位运算及其应用实例(2)
上一篇中我对位运算进行了简单介绍，并谈到了如何操作整数的位，比如将某位置0、置1、翻转、查询某位是否为1等，最后在这些基本的位操作上给出了3个位运算的应用实例。本篇是上一篇的续集，我将给出6个比较复杂一点的位操作，并对比较难以理解的位操作进行图文并茂的剖析，由于不想在一篇当中写太多内容，因此本篇中的这些位操作的实际应用案例我将在以后给出，即便是这样，本篇仍然非常重要，它是我们应用位运算来解决问题的基础。
上一篇中的四个基本位操作
1. 将expr的第n（n从0开始）位设置为1: expr |= (1<<n);
2. 将expr的第n（n从0开始）位设置为0: expr &= (~(1<<n));
3. 判断expr的第n（n从0开始）位是否为1：bool b = expr &(1<<n);
4. 翻转expr的第n（n从0开始）位：expr ^= (1<<n)；
本篇的8个较复杂的位操作
下面介绍本篇的重点：8个较复杂的位操作。要理解这些位操作并不容易，我将使用文字+图解的方式来描述，力求讲明白，需要说明的是，为了作图方便，我假设数据都是char类型(只有8个bit)，这些位操作对其他类型的数据同样适用。
1. 将最右侧的1翻转成0：x&(x-1)
假设x=01110100，那么x，x-1和x&(x-1)的二进制表示分别如下：
|
x: |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
|
x-1: |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
|
X&(x-1): |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
可以看出，x-1的功能是：将最右侧的1翻转了，并让其后的0变成了1，而保持了其他位不变。然后x&(x-1)就使得x的最右侧的1翻转成0。
该位运算在上一篇中被用来计算二进制中有多少个1，其思路是：不停的翻转右侧的1，知道将该数翻转成0为止。
2. 向右连续传播最右侧的1位：x|(x-1)
比如说x=00101000，那么x，x-1和x|(x-1)的二进制表示分别如下：
|
x: |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
|
x-1: |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
|
X|(x-1): |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
从上面的过程可以看出x|(x-1)使得x中最右边的1的右边的0都被1填充了，注意这不能理解成：翻转最右侧的连续的0，而应该理解成用最右侧的1填充了它右边的所有0位。或许你要问为什么，那么你假设x =00101001，那么x|(x-1)仍然等于00101001，它并没有将最右侧的两个0翻转！
3. 检查无符号数x是否是2的整数次幂：if((x&(x-1))==0)return true;
由1可知：x&(x-1)的作用是将最右侧的1翻转为0，假如翻转之后结果变成了0，则说明原来的数x的二进制表示中只包含一个1，那么它必定是2的整数次幂。这个简单，我就不图示了。记住:2的整数次幂跟2的整数次幂减1进行与运算的结果必然为0。
4. 检查无符号数x是否等于2的整数次幂减1：if((x&(x+1))==0) return true;
2的整数次幂减1再加1之后就等于2的整数次幂，于是可以用3的方法来判断，这也非常简单，不再图示。
5. 将右侧的连续1位串翻转成0位串，其他保持不变：((x|(x-1))+1)&x
比如x等于00101100，那么
|
x: |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
|
x-1: |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
|
X|(x-1): |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
|
(X|(x-1))+1 |
0 |
0 |
1 |
1 |
0 |
