第三节 位运算
基础知识
程序中的所有数在计算机内存中都是以二进制的形式存储的，位运算就是直接对整数在内存中的二进制位进行操作（补码且符号位也参与运算，有关补码的知识见第二章的第二节），位运算符及其运算规则如下。
按位与（&）
两个都是1才是1。例如：
00101 5 11100 28 & --------------- 00100 4
&运算通常用于二进制数的取位操作，例如一个数“& 1”的结果就是取二进制数的最末位。这可以用来判断一个整数的奇偶性，二进制的最末位为0表示该数为偶数，最末位为1表示该数为奇数。对于一个数a，a=a & (a-1)的作用是将a的二进制数最右边的1变为0。
按位或（|）
只要有一个为1就为1。例如：
00101 5 11100 28 | --------------- 11101 29
|运算通常用于二进制数特定位上的无条件赋值，例如一个数“| 1”的结果就是把二进制数最末位强行变成1。如果需要把二进制数最末位变成0，对这个数“| 1”之后再减1就可以了，其实际意义就是把这个数强行变成最接近的偶数。
按位异或（^）
相同为0，不同为1（或理解为“半加”，也就是不进位的二进制数加法）。例如：
00101 5 11100 28 ^ --------------- 11001 25
^运算可以用于简单的加密，比如我想告诉朋友我的QQ密码是123456，但又怕别人知道，所以我和朋友约定用19491001作为密钥，123456^19491001=19434233，我就把19434233告诉朋友，然后朋友再计算19434233^19491001=123456，就得到我的QQ密码了。
在密码学中，上述过程的123456称为明文，19434233称为密文，19491001称为密钥，明文经过加密过程转变为密文并传输给目标对象，目标对象接收后将密文经过解密过程转变为明文，如此便可实现安全的传输，即便被别人截获了传输的密文，没有密钥也无法得知明文。
加法的逆运算是减法，乘法的逆运算是除法，^运算的逆运算是它本身。由此可写出一个不需要中间变量的swap过程。
int a = 10,b = 5; // 原交换方法 int t = a; a = b; b = t; // 借助互逆运算 a = a + b; b = a - b; a = a - b; // 借助^ a = a ^ b; b = a ^ b; a = a ^ b;
注意：^的交换方法不能用于一个数的自我交换，会导致数据变为0。
按位取反（~）
单目运算符，1变成0，0变成1，例如：
00101 5 ~ --------------- 11010 -6
注意：11010为补码。
使用~运算时要格外小心，需要注意整数类型有没有符号。如果~的对象是无符号整数（unsigned），那么得到的值就是它与该类型上界的差。
左移（<<）
a<<b就表示把a转为二进制后左移b位（在后面添加b个0）。例如100的二进制数为1100100，而110010000转成十进制数是400，那么100<<2=400。可以看出，a<<b的值实际上就是a乘以2的b次方，因为在二进制数后添加一个0就相当于该数乘以2。
通常认为a<<1比a*2更快，因为前者是更底层一些的操作。因此程序中乘以2的操作请尽量用左移一位来代替。
定义一些常量可能会用到<<运算。你可以方便地用1<<16-1来表示65535。很多算法和数据结构要求数据规模必须是2的幂，此时可以用<<来定义Max_N等常量。
右移（>>）
与<<相似，a>>b表示把a转为二进制数后右移b位，低位舍弃b位，高位补b位符号位（正数补0、负数补1）。
右移运算对于正数，相当于a除以2的b次方（取商），想办法用>>代替除法运算可以使程序效率大大提高。
在其他编程语言（如Java）中，右移运算符分为带符号（>>）和无符号（>>>）两种。二者的区别在于舍弃低位后高位所补的数字，若带符号，则补符号位（正0负1）；若无符号，则固定补0。
位运算符优先级
速记：从高到低，反、移、与、异、或，四则运算在反、移之间。
赛题训练
1.二进制数11101110010111和01011011101011进行逻辑或运算的结果是（ ）。
A. 11111111011111
B. 11111111111101
C. 10111111111111
D. 11111111111111
2.二进制数11101110010111和01011011101011进行逻辑与运算的结果是（ ）。
A. 01001010001011
B. 01001010010011
C. 01001010000001
D. 01001010000011
3.为了统计一个非负整数的二进制形式中1的个数，代码如下：
int CountBit(int x)
{
int ret = 0;
while (x)
{
ret++;
___________;
}
return ret;
}
则空格内要填入的语句是（ ）。
A. x>>=1
B. x &=x-1
C. x |=x>>1
D. x<<=1
4.二进制数00101100和01010101异或的结果是（ ）。
A. 00101000
B. 01111001
C. 01000100
D. 00111000