题解 | #最大公约数# 库函数实现方式
最大公约数
https://www.nowcoder.com/practice/cf4091ca75ca47958182dae85369c82c
官方库函数实现方式，与大家分享
class Solution {
private:
int countr_zero(size_t x){
int res = 0;
while(x){
if(x & 1 == 0) res ++;
else break;
x >>= 1;
}
return res;
}
public:
int gcd(int m, int n) {
if (m == 0)
return n;
if (n == 0)
return m;
const int i = countr_zero(m);
m >>= i;
const int j = countr_zero(n);
n >>= j;
const int k = i < j ? i : j; // min(i, j)
while (true)
{
if (m > n)
{
int tmp = m;
m = n;
n = tmp;
}
n -= m;
if (n == 0)
return m << k;
n >>= countr_zero(n);
}
}
};
