位运算的概念和应用

位运算的概念和应用。

• 1. 位运算优先级
• 2. 位运算详解
  • 2.1 按位与
  • 2.2 按位或
  • 2.3 异或
  • 2.4 按位取反
  • 2.5 左移
  • 2.6 右移
  • 2.7 无符号右移
  • 2.8 公式总结
• 3. 位运算总结
  • 3.1 交换两个数
  • 3.2 快速最小公倍数
  • 3.3 判断奇偶
  • 3.4 符号相同
  • 3.5 第 i+1 位
  • 3.6 最低有效位
  • 3.7 绝对值

来自 LeetCode 的引述：

位操作（Bit Manipulation）是程序设计中对位模式或二进制数的一元和二元操作。

• 在许多古老的微处理器上，位运算比加减运算略快，通常位运算比乘除法运算要快很多。
• 在现代编程语言中，情况并非如此，很多编程语言的解释器都会基本的运算进行了优化，因此我们在实际开发中可以不必做一些编译器已经帮我们做好的优化，而就写出代码本身所要表现的意思。

位运算的问题，很多都很有技巧性，大家需要掌握一定的位运算的应用，达到融会贯通的目的。

大多数语言的位运算是底层而高效的，因为位运算是 CPU 支持的基本操作，大多数指令集中均支持不同类型的位运算。

我们先观察 x86 的指令语法，注释后面是等价的 C 语言语句：

xor a, b ; a ^= b;
or  a, b ; a |= b;
and a, b ; a &= b;
not a    ; ~a;

我们发现这些汇编指令和 C 语言的语句是一一对应的。说明它足够底层高效，见代码即知汇编。

注意不同语言的位运算是有区别的

• C/C++ 是由编译器处理的的，溢出不在运行时报错，但编译会报告 warning
• Java 不支持超过范围的左移操作
• JavaScript 除了大整数外，将所有的数字存储为 64 位浮点数，操作之前先将所有数字转换为 signed int32 类型，因此即使是浮点数也可以参与位运算，对于超过精度的数字会取模，对于非整数会转换为整数
• Python 的左移是无限精度的，不会出现符号变化，但如果对于大整数的左移会使程序卡死（因为程序尝试使用更大的空间表示这个巨无霸数字）

注意，不同的机器（特别是远古的）对移位操作补的数字（是 0 还是 1）有很大不同，现在的编程语言和机器对此有统一的看法，本文依照大多数情况编写。

混用符号数

不要混合使用有符号数和无符号数字进行位运算和比较运算，可能导致灾难！也不要使用不同大小（位宽度）的类型进行比较和位运算，虽然大多数情况下编译器会为你纠正！

位运算的优化

下面所说的所有技巧都是可以用但未必一定要用的技巧，你不必为了追求代码的高效而降低代码的可读性，这是得不偿失的，而且编译器做的优化会比你想象的充分。大多数场合下，你不必为每一个字节、每一个指令做优化。

1. 位运算优先级

以 C/C++ 为例，优先级如下

1. ~ 按位取反
2. + - 加减
3. << >> 位移
4. & 按位与
5. ^ 异或
6. | 按位或

不同语言的运算符优先级略有区别，总体如上所示。

2. 位运算详解

2.1 按位与

a & b 表示将相应的二进制位执行 与 运算后输出结果，因此两个负数执行后是负数，否则都是正数。

194      = 0b11000010
73       = 0b01001001
194 & 73 = 0b01000000 = 64

• 常元律 $0\ \&\ a = 0,\,(\sim 0)\ \&\ a = a$
• 交换律 $a\ \&\ b = b\ \&\ a$
• 结合律 $(a\ \&\ b)\ \&\ c =a \ \&\ (b\ \&\ c)$
• 等幂律 $a\ \&\ a = a$
• 不满足 $(a + b)\ \&\ c = (a\ \&\ c) + (b\ \&\ c)$

$\sim 0$ 等于 $-1$ ，在位运算中相等于被操作数每一位都是 $1$ ，即对于 32 位整数，表示 0xffffffff 。

技巧 1：取模

有的时候我们要取模的值可以表示为 $2^n$ ，我们发现 $a\ \%\ 2^n$ 和 $a\ \&\ (2^n-1)$ 的值总是一样的，而取模的操作的低效的（编译器也可能帮你优化），这个时候可以优化性能。例如，你需要计算 a % 4，你总是可以直接计算 a & 3 。

技巧 2：位设置

还有一个用处就是当你需要对数字 a 的某一个位设置为 0，那么使用 a & 0b1111011111111111 ，下面也会指出更简洁的方法。

2.2 按位或

a | b 表示将相应的二进制位执行 或 运算后输出结果，因此有一个负数那么结果是负数，都是正数才是正数。

194      = 0b11000010
73       = 0b01001001
194 & 73 = 0b11001011 = 203

• 常元律 $0\ |\ a = a,\,(\sim 0)\ |\ a = \sim 0$
• 交换律 $a\ |\ b = b\ |\ a$
• 结合律 $(a\ |\ b)\ |\ c =a \ |\ (b\ |\ c)$
• 等幂律 $a\ |\ a = a$
• 不满足 $(a + b)\ |\ c = (a\ |\ c) + (b\ |\ c)$

技巧 1：位设置

当你需要将某一个位设置为 1，那么你可以使用 a | 0b00001000 。

2.3 异或

a ^ b 异或的每一个二进制位是两个二进制位相等时为 0，不同时为 1。

注意，部分语言如 VB，用 ^ 表示幂，而用 XOR 表示异或。

194      = 0b11000010
73       = 0b01001001
194 ^ 73 = 0b10001011 = 139

我们用 $\oplus$ 表示异或

• 常元律 $0\ \oplus\ a = a,\,(\sim 0)\ \oplus\ a = \sim a,\,a\ \oplus\ a = 0$
• 交换律 $a\ \oplus\ b = b\ \oplus\ a$
• 结合律 $(a\ \oplus\ b)\ \oplus\ c =a \ \oplus\ (b\ \oplus\ c)$
• 自反律 $a\ \oplus\ b\ \oplus\ b = a$
• 不满足 $(a + b)\ \oplus\ c = a\ \oplus\ c + b\ \oplus\ c$

设

$$\bigoplus_{i=1}^n{a_i} = a_1 \oplus a_2 \oplus \cdots \oplus a_n$$

这表示对数组 $a_i$ 的数计算累计异或。

技巧 1：找不同

异或可以用来找不同，依据如下性质

• $a \oplus a = 0$
• $a \oplus 0 = a$

给定一个数组，除了 $x$ 每个数字都出现两次，那么所有数字异或后为 $x$ ，因为一个数字异或两次就是 0 。

技巧 2：位设置

你也可以使用异或翻转某个特定的二进制位，例如 a ^ 0b00000100000

2.4 按位取反

123  =  0b1111011
~123 = -0b1111100 = -124

~a 将每一个二进制取反，不考虑符号位，因此执行两次后这个数字还是原数 ~~x == x 。计算效果上相当于计算 $-a-1$ 。

技巧 1：位取反

你需要对全部二进制位取反，或者你想计算 $-a-1$ 的时候，使用 ~a 。

例如 ~123 = -124 ，~-124 = 123 。

2.5 左移

a << b ，逻辑左移跟算术左移完全一样，将所有二进制位向左移动，右边补 0 。效果相当于这个数字乘上 $2^k$ ， $k$ 为左移的位数。

123 << 3 = 984

技巧 1：计算幂

考虑到位移的意义，你可以使用左移进行快速乘法

• 如果你想计算 $a \times 2$ ，那么只需 a << 1 ，因为 $4 = 2^1$
• 如果你想计算 $a \times 8$ ，那么只需 a << 3 ，因为 $8 = 2^3$

有符号数的符号位也参与运算，因此最高位如果进入符号位，这个数字的符号会发生变化。

2.6 右移

12345 >> 6 = 192

a >> b 表示右移，逻辑右移跟算术右移则不一样。

大多数语言对有符号数实行算数右移，对无符号数实行逻辑右移。算数右移和逻辑右移唯一的区别是，最高位补的数字是什么

• 逻辑右移一律补 0
• 算数右移在最高位是 1 时补 1 ，在最高位是 0 时补 0

右移的效果相当于这个数字除以 $2^k$ ， $k$ 为右移的位数。

技巧 1：快速除法

快速执行除法

• 如果你想计算 $a / 2$ ，那么只需 a >> 1，因为 $1/2 = 2^{-1}$
• 如果你想计算 $a / 8$ ，那么只需 a >> 3，因为 $1/8 = 2^{-3}$

2.7 无符号右移

a >>> b 无符号右移，Java 和 JavaScript 支持无符号右移。无符号右移是对有符号数补 0 。因此执行后都是正数，除了移动 0 位。

-123       = -0b1111011
3          =  0b0000011
-123 >>> 3 =  0b11111111111111111111111110000 = 536870896

大多数语言没有无符号右移，如果你希望右移总是无符号的，请使用无符号数字参与运算。

2.8 公式总结

$$\begin{aligned} x \oplus y &= (\sim x\ \&\ y) \mid (x\ \&\ \sim y) \\ -a &= \ \sim a + 1 \\ \end{aligned}$$

3. 位运算总结

3.1 交换两个数

a ^= b;
b ^= a;
a ^= b;

3.2 快速最小公倍数

inline int gcd(int a, int b) {
    while (b ^= a ^= b ^= a %= b);
    return a;
}

3.3 判断奇偶

根据 a & 1 等价于 a % 2 。

3.4 符号相同

a ^ b >= 0

3.5 第 i+1 位

• 取出值 a & (1 << i)
• 置一 a |= 1 << i
• 置零 a &= ~(1 << i)
• 翻转 a ^ (1 << i)

3.6 最低有效位

• 获取最低有效位 a & (-a) = a & (~a + 1)

参考 位运算的性质和应用

3.7 绝对值

typedef long long ll;
#define LL_SIZE_M1 sizeof(ll) * 8 - 1

inline ll llabs(ll a) {
    return (a ^ (a >> LL_SIZE_M1)) - (a >> LL_SIZE_M1);
}

这里 LL_SIZE_M1 应当被编译器优化为常数。