知识整理
AND (&)
通常用于二进制取位操作，例如一个数 AND 1的结果就是取二进制的最末位。
小技巧
判断一个整数的奇偶，二进制的最末位为0表示该数为偶数，最末位为1表示该数为奇数： i &1
OR (|)
通常用于二进制特定位上的无条件赋值，例如一个数OR 1的结果就是把二进制最末位强行变成1。如果需要把二进制最末位变成0，对这个数OR 1之后再减一就可以了，其实际意义就是把这个数强行变成最接近的偶数。
XOR Exclusive Or (^)
若两个输入的电平相异，则输出为高电平（1）；若两个输入的电平相同，则输出为低电平（0）。
XOR Truth Table:
0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0
XOR运算的逆运算是它本身，也就是说两次异或同一个数最后结果不变，即(a XOR b) XOR b = a。
XOR运算可以用于简单的加密，比如我想对我MM说1314520，但怕别人知道，于是双方约定拿我的生日19880516作为密钥。1314520 XOR 19880516 = 20665500，我就把20665500告诉MM。MM再次计算20665500 XOR 19880516的值，得到1314520，于是她就明白了我的企图。
NOT (~)
把内存中的0和1全部取反。使用NOT运算时要需要注意整数类型有没有符号。如果NOT的对象是无符号整数（不能表示负数），那么得到的值就是它与该类型上界的差，因为无符号类型的数是用$0000到$FFFF依次表示的。
小技巧
变换符号：取反+1: (~i) + 1
SHL Shift Left (<<)
a SHL b表示把a转为二进制后左移b位（在后面添b个0），高位丢弃，低位补0。
例如100的二进制为1100100，而110010000转成十进制是400，那么100 SHL 2 = 400。可以看出，a SHL b的值实际上就是a乘以2的b次方，因为在二进制数后添一个0就相当于该数乘以2。 通常认为a SHL 1比a * 2更快，因为前者是更底层一些的操作。因此程序中乘以2的操作请尽量用左移一位来代替。 定义一些常量可能会用到SHL运算。你可以方便地用1 SHL 16 – 1来表示65535。很多算法和数据结构要求数据规模必须是2的幂，此时可以用SHL来定义Max_N等常量。
SHR Shift Right (>>)
和SHL相似，a SHR b表示二进制右移b位（去掉末b位），相当于a除以2的b次方（取整）。对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移）。我们也经常用 SHR 1来代替DIV 2，比如二分查找、堆的插入操作等等。想办法用SHR代替除法运算可以使程序效率大大提高。最大公约数的二进制算法用除以2操作来代替慢得出奇的MOD运算，效率可以提高60%。
Notes
这6种操作符，只有~取反是单目操作符，其它5种都是双目操作符；
位操作只能用于整形数据，对float和double类型进行位操作会被编译器报错；
移位操作都是采取算术移位操作，算术移位是相对于逻辑移位，它们在左移操作中都一样，低位补0即可，但在右移中逻辑移位的高位补0而算术移位的高位是补符号位。如下面代码会输出-4和3:
a, b = -15, 15
puts a >> 2
puts b >> 2因为15=0000 1111(二进制)，右移二位，最高位由符号位填充将得到0000 0011即3。-15 = 1111 0001(二进制)，右移二位，最高位由符号位填充将得到1111 1100即-4。
位操作符的运算优先级比较低，因为尽量使用括号来确保运算顺序，否则很可能会得到莫明其妙的结果。比如要得到像1，3，5，9这些2^i+1的数字。写成a = 1 << i + 1是不对的，程序会先执行i + 1，再执行左移操作。应该写成a = (1 << i) + 1;
References
Last updated