利用位运算AND计算能整除n的最大2的幂（C++）

嘿，这个问题问到点子上了！在树状数组（Binary Indexed Tree）的实现里，n & -n绝对是个“神来之笔”的操作，咱们先把它的底层原理讲透，再盘点那些日常写代码时能省事儿的位运算小技巧。

为什么 n & -n 能算出整除n的最大2的幂？ #

要搞懂这个，核心得先回忆计算机中负数的表示方式——补码：负数的补码是其原码按位取反后加1得到的。咱们分情况拆解：

情况1：n是正整数 #

假设正整数n的二进制里，最右边的1位于第k位（从0开始计数，比如n=6是0110，最右边的1在第1位）。这时候n可以写成 n = 2^k * m，其中m是奇数（因为已经把所有能提的2的幂都提出来了）。

那-n的补码怎么算？

1. 先把n的二进制按位取反：原来的...100...0（后面k个0）会变成...011...1（后面k个1）；
2. 再加1：末尾的k个1加1后会变成k个0，并且向前进一位，最终得到...100...0（后面k个0，前面的位和n的前半部分完全相反）。

这时候把n和-n做按位与运算：只有第k位上两者都是1，其余位要么n是0、-n是1，要么反过来，结果就是2^k——正好是能整除n的最大2的幂。

举个例子：n=6（0110），-6的补码是1010，0110 & 1010 = 0010（也就是2），完全符合预期。

情况2：n是0或者负数 #

• n=0时，0 & -0结果还是0，不过树状数组里一般不会用到0作为索引，所以不用太在意；
• n是负数时，本质和正整数逻辑一致，n & -n得到的是能整除|n|的最大2的幂，比如n=-6（补码1010），-n=6（0110），按位与结果还是2。

那些实用的位运算技巧 #

位运算因为直接操作二进制，速度比普通算术运算快很多，日常开发里有不少高频好用的技巧：

• 1 << n：快速计算2的n次幂，比如1 << 3就是8。注意如果n超过变量类型的位数会溢出（比如32位int的话，1 << 31会得到负数）。
• n >> 1：等价于对n做整数除法除以2，不过是向下取整，比如5 >> 1 = 2，-5 >> 1 = -3（补码右移会填充符号位）。
• n & 1：判断n是奇数还是偶数，结果为1就是奇数，0就是偶数，比n % 2快不少。
• n | 1：把n转换成最近的奇数，比如4 | 1 = 5，5 | 1 = 5。
• n ^ n：结果恒为0，常用于快速清空变量，或者判断两个数是否相等（如果a ^ b == 0，则a和b相等）。
• n ^ (n >> 1)：生成对应的格雷码（Gray Code），比如n=3（011），n >> 1 = 1（001），异或后得到010，就是3对应的格雷码。
• n & (n - 1)：消除n二进制中最右边的1，比如n=6（0110），n-1=5（0101），按位与得到0100（4）。这个技巧可以用来统计二进制中1的个数（循环消除直到n为0，计数次数就是1的数量），也能快速判断n是不是2的幂（如果n & (n-1) == 0且n != 0，那n就是2的幂）。
• n | (n - 1)：把n二进制中最右边的所有0都变成1，比如n=6（0110），n-1=5（0101），按位或得到0111（7）。
• (n ^ m) & -(n ^ m)：找到n和m二进制中第一个不同的位，原理和n & -n完全一致，异或后最右边的1就是两者第一个不同的位置。

内容的提问来源于stack exchange，提问作者yagyanshbhatia