位运算 - 千反田

计算机采用的是二进制，二进制包括两个数码：0,1。在计算机的底层，一切运算都是基于位运算实现的。

位运算共有 6 种，分别是：与、或、异或、取反、左移和右移，其中左移和右移统称移位运算，移位运算又分为算术移位和逻辑移位。

上述位运算中，只有取反是一元运算，其余的都是二元运算。

与、或、异或和取反

移位运算按照移位方向分类可以分成左移和右移，按照是否带符号分类可以分成算术移位和逻辑移位。

左移运算的符号是 $<<$ 。左移运算时，将全部二进制位向左移动若干位，高位丢弃，低位补 0。对于左移运算，算术移位和逻辑移位是相同的。
右移运算的符号是 $>>$ 。右移运算时，将全部二进制位向右移动若干位，低位丢弃，高位的补位由算术移位或逻辑移位决定：
- 算术右移时，高位补最高位；
- 逻辑右移时，高位补 0。

C++ 中：
对于有符号类型，右移运算为算术右移；对于无符号类型，右移运算为逻辑右移。
Java 中：
不存在无符号类型，所有的表示整数的类型都是有符号类型，因此需要区分算术右移和逻辑右移。
算术右移的符号是 $>>$，逻辑右移的符号是 $>>>$
Go 中：
只有算数移位

使用移位运算实现乘除法的效率显著高于直接乘除法的效率。

左移运算对应乘法运算。将一个数左移 k 位，等价于将这个数乘以 $2^k$
- 例如，$29 << 2 = 116$，等价于 $ 29 \times 4 $
- 当乘数不是 2 的整数次幂时，可以将乘数拆成若干项 2 的整数次幂之和：
  
  例如，$a \times 6$ 等价于 $(a<<2)+(a<<1)$
- 对于任意整数，乘法运算都可以用左移运算实现，但是需要注意溢出的情况，例如在 8 位二进制表示下，29 左移 3 位就会出现溢出。
算术右移运算对应除法运算。将一个数右移 k 位，相当于将这个数除以 $2^k$
- 例如，$50 >> 2 = 12$ ，等价于 $50 / 4$，结果向下取整
- 一个数（算术）右移 k 位，和将这个数除以 $2^k$ 是不等价的（只对 0 和正数成立）

同时，位运算也能用来替代取模运算判断奇偶：

此处列举位运算中的与、或、异或和取反的常见性质。假设以下出现的变量都是有符号整数。

幂等律：$a \And a = a$ ，$a ∣ a=a$ （注意异或不满足幂等律）
交换律：$a \And b = b \And a$，$a ∣ b = b ∣ a$，$a \oplus b = b \oplus a$
结合律：$(a \And b) \And c = a \And (b \And c)$，$(a ∣ b) ∣ c = a ∣ (b ∣ c)$，$(a \oplus b) \oplus c = a \oplus (b \oplus c)$
分配律：$(a \And b) ∣ c = (a ∣ c) \And (b ∣ c)$，$(a ∣ b) \And c = (a \And c) ∣ (b \And c)$，$(a ⊕ b) \And c = (a \And c) ⊕ (b \And c)$
德·摩根律：$\sim (a \And b) = ( \sim a) ∣ (\sim b)$ ，$\sim(a ∣ b) = (\sim a) \And (\sim b)$
取反运算性质：$-1 = \sim 0，-a = \sim (a-1)$
与运算性质：$a \And 0 = 0$，$a \And (-1) = a$，$a \And (\sim a) = 0$
或运算性质：$a ∣ 0 = a$，$a ∣ (\sim a) = -1$
异或运算性质：$a \oplus 0 = a$，$a \oplus a = 0$
其他性质：
- $a \And (a-1)$ 的结果：将 a 的二进制表示的最后一个 1 变成 0
- $a \And (-a)$（与 $a \And (\sim (a-1))$ 等价）的结果：只保留 a 的二进制表示的最后一个 1，其余的 1 都变成 0