# 知识整理

## 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

{% embed url="<http://www.matrix67.com/blog/archives/263>" %}

{% embed url="<https://blog.yangx.site/2016/07/06/bit-operation-skills/>" %}
