如何理解位与运算表达式n & (n - 1)？

核心原理 #

n & (n - 1)的本质是消除n的二进制表示中最右侧的那个1，逻辑很直接：

• 对n减1时，二进制里最右边的1会被翻转为0，它右侧所有的0都会被翻转为1，左侧的位保持不变。
• 用原n和减1后的n做位与运算，左侧不变的位会保留，而最右边的1及其右侧的位会全部变为0，相当于直接把最右边的1“抹掉”。

举几个直观例子：

• n=8（二进制1000），n-1=7（0111），8 & 7 = 0——最右边的1被消除，结果为0。
• n=6（二进制0110），n-1=5（0101），6 & 5 = 4（0100）——最右边的1（第二位）被消除，剩下左边的1。
• n=9（二进制1001），n-1=8（1000），9 & 8 = 8（1000）——最右边的1（第一位）被消除。

常见实用场景 #

• 判断n是否是2的整数次幂：如果n是2的幂，它的二进制里只有一个1，执行n & (n-1)后结果必然是0；反之如果结果不为0，说明n不是2的幂。比如8 & 7 = 0（是2的幂），6 & 5 = 4 ≠ 0（不是）。
• 统计二进制中1的个数：循环执行n = n & (n-1)，每执行一次就消除一个1，直到n变为0，循环的次数就是二进制中1的总数。比如n=6（0110），第一次循环后n=4，第二次循环后n=0，共2次，对应2个1。
• 快速定位最低位1的数值：用n - (n & (n-1))可以直接得到n的二进制中最右侧1对应的值。比如n=6，6 - 4 = 2，正好是最右侧1的数值。

内容的提问来源于stack exchange，提问作者Penny M.