官方库函数实现方式,与大家分享
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); } } };