二进制GCD

目录

• 写在前面
• 具体实现：
• Code

写在前面

全程抄书

想要进一步提高求 (gcd) 的效率，可以通过不断去除因子 (2) 来降低常数，这就是“二进制 (gcd) ”

具体实现：

若 (x = y) ，则 (gcd(x, y) = x) 否则：

• 若 (x, y) 均为偶数，则 (gcd(x, y) = 2 * gcd(x / 2, y / 2))

• 若 (x) 为偶数， (y) 为奇数， 则 (gcd(x, y) = gcd(x / 2, y))

• 若 (x) 为奇数， (y) 为偶数， 则 (gcd(x, y) = gcd(x, y / 2))

• 若 (x, y) 均为奇数，则 (gcd(x, y) = gcd(x - y, y))

Code

int Gcd(int x, int y){//二进制GCD 
	int i = 0, j = 0;
	if(x == 0) return y;
	if(y == 0) return x;
	while((x & 1) == 0) x >>= 1, ++i;
	while((y & 1) == 0) y >>= 1, ++j;
	if(j < i) i = j;
	while(1){
		if(x < y) x ^= y, y ^= x, x ^= y;
		if(0 == (x -= y)) return y <<= i;
		while(0 == (x & 1)) x >>= 1; 
	}
}