How the following function of finding GCD of two numbers using bitwise operation works?

I found this function on the internet while searching for a solution for a problem. I tested it and it seems to be working fine. I just need to know how this works. Is this more efficient than the common way of finding GCD? Here is the function:

int gcd(int a,int b){
    while(b)
       b^=a^=b^=a%=b;
    return a;
}

Solution

This code just implements Euclid's algorithm for finding the greatest common denominator (GCD). I'd say it is pretty darn standard, given that it's been widely known and used since ~300 BC. I'm not sure what other algorithm you are comparing it to when you say "the common way of finding GCD", but Euclid's algorithm is known to be an efficient one.

The only thing weird about this code is that it has been heavily obfuscated. Someone thought they were being clever by compressing all the code onto one line, but unless you're getting paid a bonus based on the number of lines of code that you delete, there's no point in doing this. It doesn't change the object code generated by the compiler; it just makes your source more difficult to read and understand.

And actually, the obfuscation that was done here introduces serious bugs into the code, assuming that this is C or C++. The operations on a and b are undefined because of a lack of sequence points.

Another "clever" technique that this code uses is a bitwise XOR to swap values without using a temporary. This is a very old trick, so old that it hasn't been a worthwhile "optimization" in many years. In fact, it is very likely slower than just using a temporary variable. There are lots of descriptions of how it works online. It looks complicated but is actually pretty simple, so lots of people have blogged about it.

Ungolfed, the code you have is just the following:

int gcd(int a,int b) {
    while(b)              // while b is non-zero
    {
       int temp = b;      // cache current value of b
       b = (a % b);       // set b equal to (a modulo b)
       a = temp;          // set a equal to the original value of b
    }
    return a;             // once b is zero, return a
}

Note that the code can also be written recursively:

int gcd(int a,int b) {
    if (b)
        return gcd(b, a % b);
    else
        return a;
}