做题时用到了按位异或的操作，有点蒙蒙的，大概查了查位运算的一些东西，略作总结，主要以Python为例。
位运算简介
位运算是把数字用二进制表示之后，对每一位上0或1的运算。
所有的运算（包括位运算）在计算机内部都是通过补码的形式进行运算的。
补码是计算机表示数据的一般方式，其规则为：如果是正数，则表示方法和原码一样；如果是负数，则将数字的反码加上1(相当于将原码数值位取反然后在最低位加1)。
例如：
数字 6 在8位计算机中的补码为：0000 0110 （即为其原码）
数字 -6 在8位计算机中的补码为：1111 1010
主要的位运算总共有6种：与、或、异或、取反、左移、右移，如下表所示：
表中示例：
a=60，二进制表示 0011 1100
b=13，二进制表示 0000 1101
| 运算符 | 描述 | 示例 | ||
|---|---|---|---|---|
| & | 按位与：参与运算的两个值，如果两个对应位都为1，则该位的结果为1，否则为0； | (a&b)结果为12，二进制 0000 1100 | ||
| \ | 按位或：只要对应的两个二进制位中有一个为1时，该位的结果就为1； | (a\ | b)结果为61，二进制 0011 1101 | |
| ^ | 按位异或：当两个对应的二进制位不同时，该位的结果为1； | (a^b)结果为49，二进制 0011 0001 | ||
| ~ | 按位取反：对数据的每个二进制位取反，即把1变成0，把0变成1； | (~a)结果为 -61，二进制 1100 0011（有符号二进制数的补码形式） | ||
| \<\< | 按位左移：数据的每个二进制位均左移若干位，\<\<右边的数字指定移动位数，高位丢弃，低位补0； | (a\<\<2)结果为240，二进制 1111 0000 | ||
| >> | 按位右移：数据的每个二进制位均右移若干位，>>右边的数字指定移动位数，具体见下文； | (a>>2)结果为15，二进制 0000 1111 |
左移运算符：m\<\<n 表示把 m 左移 n 位，最左边的 n 位被丢弃，同时在最右边补上 n 个0，如下：
1
200001010 << 2 = 00101000
10001010 << 3 = 01010000右移运算符：m>>n 表示把 m 右移 n 位，最右边的 n 位被丢弃，但最左边的处理方式有所不同：如果符号位为0，则右移后高位补0，如果符号位为1，则高位补1，也就是说，如果数字是正数，则右移后在最左边补 n 个0，如果数字为负数，则右移后在最左边补 n 个1。如下：
1
200001010 >> 2 = 00000010
10001010 >> 3 = 11110001
如下为Python中所有位运算操作符示意：
1 | a = 60 # 60 = 0011 1100 |
移位运算
运算规则
左移运算符：m\<\<n 表示把 m 左移 n 位，最左边的 n 位被丢弃，同时在最右边补上 n 个0，如下：
1
200001010 << 2 = 00101000
10001010 << 3 = 01010000右移运算符：m>>n 表示把 m 右移 n 位，最右边的 n 位被丢弃，但最左边的处理方式有所不同：如果符号位为0，则右移后高位补0，如果符号位为1，则高位补1，也就是说，如果数字是正数，则右移后在最左边补 n 个0，如果数字为负数，则右移后在最左边补 n 个1。如下：
1
200001010 >> 2 = 00000010
10001010 >> 3 = 11110001
特殊应用
移位运算是最有效的计算乘/除法的运算之一，把整数左/右移一位，和把整数乘以/除以 2 在数学上是等价的。
1
2
3
4
5
6
7
8
9
10
11a = 2
print a << 1 # 左移一位等效于a = a * 2;
# result: 4
print a << 2 # a左移两位等效于a = a * 2的2次方（4）；
# result: 8
a = 16
print a >> 1 # 右移一位等效于a = a / 2；
# result: 8
print a >> 2 # 右移两位等效于a = a / (2**2)；
# result: 4
按位与
运算规则
0&0=0，0&1=0，1&0=0，1&1=1。
即：两位同时为“1”，结果才为“1”，否则为0，有0则0。
特殊应用
清零指定位：
mask中指定位置0，其它位为1，
a = a & mask。取一个数的指定二进制位：
mask中指定位置1，其它位为0，
a = a & mask。判断一个数二进制表示中1的个数：
一个整数减去1，再和原数做与运算，会把该整数二进制表示中最右边一个1变为0。
如：
实现一个函数，输入一个正数，输出该数二进制表示中1的个数：
1
2
3
4
5
6
7
8num = 0
n=5 # 二进制：101
while(n):
n &= (n-1)
num += 1
print str(num)
# result: 2判断一个正数是不是2的整数次方：
如果是2的整数次方，则其二进制表示中有且只有一位是1。
1
2
3
4a=4
print a&(a-1) == 0
# result: True
按位或
运算规则
0|0=0；0|1=1；1|0=1；1|1=1。
即 ：参加运算的两个对象只要有一个为1，其值为1，有1则1。
特殊应用
对数据的指定位置为1：
mask指定位置1，其它位为0，
a = a | mask。如：将
a = 1010 0000低四位置1，则a | 0000 1111即可。
按位异或
运算规则
0^0=0；0^1=1；1^0=1；1^1=0。
即：参加运算的两个对象，如果两个相应位为“异”（值不同），则该位结果为1，否则为0，同0异1。
异或特点：
0异或任何数均为原数
1异或任何数，结果为对该数取反
- 任何数异或自己，结果为0
特殊应用
使特定位翻转：
mask的特定位置1，其它位为0，
a = a ^ mask。如，对数10100001的第2位和第3位翻转，则可以将该数与00000110进行按位异或运算：
10100001^00000110 = 10100111。不使用临时变量，交换两个数的值：
如，交换两个整数a=10100001，b=00000110的值：
1
2
3a = a^b # a=10100111
b = b^a # b=10100001
a = a^b # a=00000110与0异或，保留原值：
a ^ 0仍为a。