数学类问题一定要记得进位 v = v1 + v2 + carry

最大公约数和最小公倍数

辗转相除法（欧几里得算法）. 原理在于 gcd(a, b) == gcd(b, a % b)

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

排列组合

卡特兰数，为什么除以 n+1

牛顿迭代法

格雷码

二进制

• 判断一个数是不是 2 的正整数次幂：n > 0 && (n & (n - 1)) == 0
• 对 2 的非负整数次幂取模：x & (mod - 1)
• 判断符号是否相同：(x ^ y) >= 0
• 获取某一位：(a >> b) & 1
• 遍历某个集合的子集：for (int s = u; s; s = (s - 1) & u)
• 一的个数：while (n) {n = n & (n-1); count++}

求幂

long long binpow(long long a, long long b) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a;
    a = a * a;
    b >>= 1;
  }
  return res;
}

全排列

几何

有时候几何题也会出现在面试中。不过，毕竟是 coding interview 而不是 math interview，这部分复习的优先级不高。

参考

• https://oi-wiki.org/math/
• https://www.zhihu.com/question/26094736
• https://web.archive.org/web/20170215121714/http://noalgo.info/414.html