[LeetCode] Bit 操作

本文介绍几种差用的位操作：

n = n & (-n)

n = n & (-n) 能取出最右端为'1'的位。比如：
22 =
0000 0000 0000 0000 0000 0000 0001 0110
-21 =
1111 1111 1111 1111 1111 1111 1110 1001 (先各位取反，包括符号位)
1111 1111 1111 1111 1111 1111 1110 1010 (再末位+1)
21 & (-21) =
0000 0000 0000 0000 0000 0000 0000 0010
21的最后一个1保留，其他全部为0。

相关题目

260 Single Number III
https://leetcode.com/problems/single-number-iii/solution/

n = n & (n – 1)

n & (n – 1) 总是能清除最后一位bit。比如：n=112

n=112的例子

可以用来计算n有几个1。

// 记录数字中1的位数  
int bitCount(int n) {
    int count = 0;
    // 数字的二进制表示中有多少个1就进行多少次操作  
    while (n != 0) {
        // 从最右边的1开始，每一次操作都使n的最右的一个1变成了0，即使是符号位也会进行操作。  
        n &= n - 1;
        count++;
    }
    return count;
}

相关题目

231 Power of Two
https://leetcode.com/problems/power-of-two/

---

本文参考：https://tech.liuchao.me/2016/11/count-bits-of-integer/ - 推荐