'Erik said:
Just since no one seems to have mentioned it yet.. this is a Greatest common divisor problem. Google gave me the following code for it, if shorter is better.
unsigned b_gcd(unsigned a, unsigned b) {
while (B) b ^= a ^= b ^= a %= b;
return a;
}
So if you have Width x Height, just divide them both by GCD(Width, Height).
(Guess we found another bug in the source view.. cause those B's were entered as lower case b's :)
That code blows my mind. I thought I understand C pretty well, but I don't understand that.
Anyway, nice thread, thanks guys!
I guess that every body understands a %= b, so the critical part is the b^=a^=b^=a.
So let's rewrite this as the compiler will rewrite it
while (b)
{
a %= b;
b ^= a; // XOR
a ^= b; // XOR
b ^= a; // XOR
}
Those who know the shortcut might understand that the 3 last lines is a swap(a,B). For those who don't, remember that XOR is
* associative : a XOR b XOR c = (a XOR b) XOR c = a XOR (b XOR c)
* commutative : a XOR b = b XOR a
Let's restart from the begining:
b1 = b0 XOR a0
a1 = a0 XOR b1 => a1 = a0 XOR (b0 XOR a0) => a1 = (a0 XOR a0) XOR b0 ==> a1 = b0
b2 = b1 XOR a1 => b2 = b1 XOR (a0 XOR b1) => b2 = (b1 XOR b1) XOR a0 ==> b2 = a0
So what we effectively do is:
while (b)
{
a %= b;
std::swap(a,b)
}
Which is, in essence,
Euclid's recursive algorithm written as an iterative loop. In a single, cryptic line of code :)
PS: the b which becomes B is not a bug in the source view ; it's a feature (emoticon's replacement). Which is even more annoying.
Can't this be removed? Emoticons are better when they are used on purpose.