位运算

参考：位操作

概念

位运算是程序设计中对位模式或二进制数的一元和二元操作。在许多古老的微处理器上，位运算比加减运算略快，通常位运算比乘除法运输要快很多。在现代架构中，情况并非如此：位运算的运算速度通常与加法运算相同（仍然快于乘法运算）。

位运算符

取反（NOT）

取反是一元运算符，对一个二进制数的每一位执行逻辑反操作。是数字 1 成为 0，0 成为 1。例如：

NOT 0111（十进制 7）
= 1000（十进制 8）

许多程序设计语言（包括 C 程序设计语言 family），取反操作符用波浪线 ~ 表示。值得注意的是此操作符与「逻辑非（!）」操作符不同。在 C++ 中，逻辑非将数字整体看做一个布尔类型—将真值转化为假，将假值转化为真；而 C 语言将 0 转化为 1，将非零转化为 0。「逻辑非（!）」并不是一个位操作。

按位或（OR）

按位或处理两个长度相同的二进制数，两个相应的二进位中只要有一个为 1，该位的结果值为 1。例如：

   0101（十进制5）
OR 0011（十进制3）
 = 0111（十进制7）

在 C 类程序设计语言中，按位或操作符是 | 。这一操作符需要与逻辑或运算符（||）区别开来。

按位异或（XOR）

按位异或运算 ，对等长二进制模式或二进制数的每一位执行逻辑异或操作。操作的结果是如果某位不同则该位为 1，否则该位为 0；例如：

    0101
XOR 0011
  = 0110

在类 C 语言中，按位异或运算符是 ^。

汇编语言的程序员们有时使用按位异或运算 作为。将寄存器的值设为 0 的捷径。用值的自身对其执行按位异或运算将得到 0。并且 在许多架构中，与直接 记载 0 值并将它保存到寄存器相比，按位异或运算需要较少的中央处理单元时钟周期。

按位异或也可以用于在比特集合中切换旗帜。

    0010
XOR 1010
  = 1000

0010 第一位和第三位能够 通过 按位 异或运算使用同时切换。这一技巧 可用于操作表示布尔变量的比特模式。

按位与（AND）

按位与处理两个长度相同的二进制数，两个相应的二进位都为 1，该位的结果值才位 1，否则为 0。例如：

    0101
AND 0011
  = 0001

在类 C 语言中，按位与用 & 表示。

移位

移位是一个二元运算符，用来将一个二进制数中的每一位全部都向一个方向移动指定位，溢出的部分将被舍弃，而空缺的部分填入一定的值。在类 C 语言中，左移使用两个小于符号 << 表示，右移使用两个大于符号 >> 表示。

逻辑移位

应用逻辑移位时，移位后空缺的部分全部填 0。

    0001（十进制 1）
 <<    3（左移 3 位）
  = 1000（十进制 8）

    1000（十进制 10）
 >>    2（右移 2 位）
  = 0010（十进制 2）

Java 中的移位

Java 中有一个特有的无符号右移操作符 >>>。此操作将忽略操作数的符号，同样的还有 >>>=。

指定位置的位运算

1. 将 x 最右边的 n 位清零：x & (~0 << n)

2. 获取 x 的第 n 位值（0 或者 1）： (x >> n) & 1

3. 获取 x 的第 n 位的幂值：x & (1 << (n -1))

4. 仅将第 n 位置为 1：x | (1 << n)

5. 仅将第 n 位置为 0：x & (~ (1 << n))

6. 将 x 最高位至第 n 位（含）清零：x & ((1 << n) - 1)

7. 将第 n 位至第 0 位（含）清零：x & (~ ((1 << (n + 1)) - 1))

实战位运算要点

• 判断奇偶：
  x % 2 == 1 —> (x & 1) == 1
  x % 2 == 0 —> (x & 1) == 0
• x >> 1 —> x / 2
  即： x = x / 2; —> x = x >> 1;
  mid = (left + right) / 2; —> mid = (left + right) >> 1;
• X = X & (X-1) 清零最低位的 1
• X & -X => 得到最低位的 1
• X & ~X => 0