从CSAPP的第一个lab开始，知道了位运算，知道了位运算的厉害之处。最近在做一些算法题目的时候，也接触了一些常用的位运算的小Trick，于是就记录下。
修改最右边的1
y = x & (x - 1)
这个方法是位运算非常有趣的应用，x - 1与x之前的区别，在于x最右边的1会变成0，其后的0会全变成1，这样做一个按位与的操作，就会使得最右的1变为0。
示例
01010111 (x)
& 01010110 (x-1)
--------
01010110
01011000 (x)
& 01010111 (x-1)
--------
01010000
10000000 (x = -128)
& 01111111 (x-1 = 127 (with overflow))
--------
00000000
11111111 (x = all bits 1)
& 11111110 (x-1)
--------
11111110
00000000 (x = no rightmost 1-bits)
& 11111111 (x-1)
--------
00000000
应用
这个方法可以用来统计二进制位一共有多少个1，时间复杂度为O(m)，m为二进制位中1的个数。
int hammingWeight(uint32_t n)
{
int res = 0;
while(n)
{
n &= n - 1;
++ res;
}
return res;
}
扩展
这个问题可以归结为一类问题，那就是在不改变最右边的1之前的位的情况下，对最右1以及其左边的位做一些改变。这种问题都离不开x - 1。比如，当需要把最右1之后的所有数字都变成1的时候，可以：
y = x | (x - 1)
取出最右的1
y = x & (-x)
这个做法，是利用了补码与原码之间的关系。-x与x之间的关系在于-x = ~x + 1，所以-x与x之间，只有最右边的1是完全一样的，所以做了按位与之后，得到的就只有最右的1。
示例
10111100 (x)
& 01000100 (-x)
--------
00000100
01110000 (x)
& 10010000 (-x)
--------
00010000
00000001 (x)
& 11111111 (-x)
--------
00000001
10000000 (x = -128)
& 10000000 (-x = -128)
--------
10000000
11111111 (x = all bits one)
& 00000001 (-x)
--------
00000001
00000000 (x = all bits 0, no rightmost 1-bit)
& 00000000 (-x)
--------
00000000
修改最右的0
y = x | (x + 1)
这个跟前面的修改最右1有异曲同工之妙，也是利用了x与x + 1的关系。两者的二进制表示，区别是x + 1的最右的0变成了1，其后的1都变成了0。所以再来一个按位或，能够实现修改最右的0。
示例
10111100 (x)
| 10111101 (x+1)
--------
10111101
01110111 (x)
| 01111000 (x+1)
--------
01111111
00000001 (x)
| 00000010 (x+1)
--------
00000011
10000000 (x = -128)
| 10000001 (x+1)
--------
10000001
11111111 (x = no rightmost 0-bit)
| 00000000 (x+1)
--------
11111111
00000000 (x)
| 00000001 (x+1)
--------
00000001
更多
还有更多有意思的Trick，可以去CSAPP-Lab1看看。