位运算相关技巧

这里想记录一些在做题过程中遇到的位运算相关技巧。

##二进制表示中最低位

在位运算相关的题目中，有很多会与位 1 的个数相关。这里有个相关的小技巧。

cpp[copy]
n & (n-1)

通过以上表达式可以将 n 二进制表示的最低位 1 移除。原理是最低位1后会跟一些0。即 $100000_2$ , 将他减一后，得到 $011111_2$ 这两数相与便可以将最后一位 1 移除，而其他位 1 不受影响。

这个技巧可以运用在很多地方，比如我们想统计数n中1的数量。
可以直接让n与n-1相与，直到n=0。代码如下：

cpp[copy]
while (n) {
    n &= n - 1;
    ret++;
}

##判断是否是2的幂

利用

cpp[copy]
(n&(-n))==n

可以用来判断正整数n是否是2的幂，利用计算机补码知识，可以知道-n即为n所有位取反加一，记最后一位 1 前的高位为 $a$ （n为2的幂时全为0），n即 $a10000_2$ ，而 -n 为 $\overline{a}01111 + 1$ ，即 $\overline{a}10000$ ，所以当n为2的幂时， n 和 -n 相与后仍然得到 n 。

##注意

在进行位运算时，要时刻注意位运算优先级较低，以上面判断是否是2的幂为例，应该使用

cpp[copy]
(n&(-n))==n

而不是

cpp[copy]
n&(-n)==n

后者会先运算 (-n)==n 。

附上c++运算符优先级表: