LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 对一个数和比它小 1 的数做与运算，即可消除这个数二进制最低位的 1

最低位是 1，则等价于把最低位的 1 改为 0
1111 & 1110 = 1110
1011 & 1010 = 1010
xxx1 & xxx0 = xxx0

最低位不是 1，则找到最低位的 1，比它小 1 的数该位为 0，之后为 1
1110 & 1101 = 1100
1100 & 1011 = 1000
1000 & 0111 = 0000

  xxx100000...（n 个 0）
& xxx011111...（n 个 1）
= xxx000000（n + 1 个 0）

• 逐次消除最低位的 1 直到值为 0，消除的次数即为结果

class Solution {
 public:
  int hammingWeight(uint32_t n) {
    int res = 0;
    while (n) {
      ++res;
      n &= n - 1;
    }
    return res;
  }
};