备忘 - 常用子函数

暴力搜索

遍历所有子集

• 代码
• imhuay/AlgorithmforInterview/_utils工具函数/遍历所有子集.hpp
• 相关问题

遍历所有正因子

• 代码
• imhuay/AlgorithmforInterview/_utils工具函数/遍历所有正因子.hpp
• 相关问题

二分查找

离散模板

连续模板

位运算

• 代码
• imhuay/AlgorithmforInterview/_utils工具函数/位运算.hpp

计算二进制表示中 1 的个数

法 1：O(m) - m 为 1 的个数

  int numberOfOne(int n) {
      int cnt = 0;
      while (n > 0) {
          cnt++;
      }
      return cnt;
  }
  /* 说明：
      n-1 后会翻转右数第一个 1 及之后的每一位；
      然后 n&(n-1) 会把该位置的 1 及之后的每一位置零；
      因此每次循环恰好消去一个 1 直到变为 0
          n       = 100,100
          n-1     = 100,011
      n = n&(n-1) = 100,000   cnt++
          n-1     = 011,111
      n = n&(n-1) = 000,000   cnt++
  */

法2：O(n) - n 为二进制的长度

  int numberOfOne(int n) {
      int cnt = 0;
      while (n > 0) {
          if (n & 1)
              cnt++;
          n >>= 1;
      }
      return cnt;
  }
  /* 说明：
      每次移动一位，判断是否为 1
  */

判断第 i 位是否为 1

构造一个第i位是1的数与原数做与运算

  int i = 4;  // 因为 i 从 0 开始，所以这实际上是右起第 5 位
  int n = 16; // 10000
  // 法 1：移动 1
  if (n & (1 << i))
      cout << "true" << endl;
  // 法 2：移动 n
  if ((n >> i) & 1)
      cout << "true" << endl;

置第i位为 1 且不影响其他位

类似判断第i位是否为 1的思路

int ret = 3;  // 011
int i = 2;
ret ^= 1 << i;  // 111

判断奇偶

判断奇偶，实际上就是判断二进制表示的最后一位是否为 1

  n = 5;
  if (n & 1)  // 只适用于正整数，但是效率更高
      cout << n << " 是奇数" << endl;

  // 常规方法
  if (n % 2 != 0)  // 适用于正、负数
      cout << n << " 是奇数" << endl;

简单快速幂

double quickPow(double base, int p) {
    double ret = 1.0;
    int q = abs(p);
    while (q > 0) {
        if (q & 1)
            ret *= base;
        base *= base;
        q >>= 1;
    }
    return p > 0 ? ret : 1 / ret;
}

• 用一个例子来说明这段代码更直观
• 求 3^20 = 9^10 = 81^5 (= 81*81^4) = 81*6561^2 = 81*43046721
• 循环次数 = bin(20)的位数 = len(10100) = 5