摘录自《算法新的-高效算法的奥秘（第二版）》

操作最右边的位元

将字组中值为 1 且最靠右的位元“关闭”，如果不存在值为 1 的位元，那结果就是 0（例如 01011110 => 01010000）：

1
x & (x一1)

该操作可判断某个无符号整数是不是 2 的幂或 0：套用此公式后判断运行结果是否为 0 即可。

将字组中值为 0 且最靠右的位元“打开”，如果不存在值为 0 的位元，则结果的每一位都是 1（例如 10100111 => 10101111）：

1
x | (x+1)

将字组尾部的 1 都变成 0，如果尾部没有 1，则x不变（例如 10100111 => 10100000）：

1
x & (x+1)

套用此公式后判断结果是否为 0，即可确定某个无符号整数是不是 2^n^-1 或 0，也可以判断某个数的所有位元是否均为 1。

将字组尾部的 0 都变成 1，如果尾部没有 0，则 x 不变（例如10101000 => 10101111）：

1
x | (x-1)

把 x 中最靠右且值为 0 的位元变为 1，并将其余位元置 0。如果x中没有值为 0 的位元，则结果为 0（例如 10100111 => 00001000）：

1
!x & (x+1)

把 x 中最靠右且值为 1 的位元变成 0，并将其余位元置 1。如果 x 中没有值为 1 的位元，则运算结果中的每个位元均是 1（例如 10101000 => 11110111）：

1
!x | (x-1)

下列 3 个公式都可以把字组尾部所有值为 0 的位元变成 1，并将其余位元置 0。如果 x 中没有值为 0 的位元，则结果是 0（例如 01011000 => 00000111）：

1
2
3
!x & (x-1)
!(x | -x)
(x & -x) - 1

第 1 个公式可以发挥处理器的某些指令级并行能力。

下列公式可以把字组尾部所有值为 1 的位元都变成 0，并将其余位元设为 1。如果 x 中没有值为 1 的位元，则运算结果中的每个位元均是 1（例如 10100111 => 11111000）：

1
!x | (x+1)

下列公式可以保留字组中最靠右且值为 1 的位元，并将其余位元置 0。若 x 不存在值为 1 的位元，则运算结果为 0（例如 01011000 => 00001000）：

1
x & (-x)

下列公式可以将字组最靠右且值为 1 的位元，及其右方所有值为 0 的位元都变成 1，并将左方位元置 0。若 x 中没有值为 1 的位元，则运算结果的每一位都是 1，而当x尾部没有值为 0 的位元时，运算结果是 1（例如 01011000 => 00001111）：

1
x ^ (x-1)

下列公式可以将字组最靠右且值为 0 的位元，及其右方所有值为 1 的位元都设为 1，并将左方位元置 0。若 x 中没有值为 0 的位元，则运算结果的每一位都是 1，而当 x 尾部没有值为 1 的位元时，运算结果是 1（例如 01010111 => 00001111）：

1
x ^ (x+1)

下列两个公式都可以把字组右侧连续出现且值为 1 的位元置 0（例如 01011100 => 01000000）：

1
2
( (x | (x-1)) + 1) & x
(x & -x) + x

如果 x 是非负数，而且套用上述公式运算的结果是 0，那就表明它可以写为 2^j^-2^k^ 的形式。其中 j ≥ k ≥ 0。

德摩根定律及推论

描述德摩根定律的两个逻辑恒等式可以理解为把取反符号（not sign）“分配”到每一个变量中。结合下列等式（头两个就是德摩根定律）与德摩根定律的思路，可以为所讲的公式及其他一些公式变形。

1
2
3
4
5
6
7
8
9
!(x & y) = !x | !y
!(x | y) = !x & !y
!(x + 1) = !x - 1
!(x - 1) = !x + 1
!-x = x - 1
!(x ^ y) = !x ^ y = x ≡ y
!(x ≡ y) = !x ≡ y = x ^ y
!(x + y) = !x - y
!(x - y) = !x + y

上述公式可以这样用：

1
!(x | -(x + 1)) = !x & !-(x + 1) = -!x & ((x + 1) - 1) = !x & x = 0

结合逻辑操作的加减运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
-x = !x + 1
   =!(x - 1)
!x = -x - 1
-!x = x + 1
!-x = x - 1
x + y = x - !y - 1
      = (x ^ y) + 2(x & y)
      = (x | y) + (x & y)
      = 2(x | y) - (x ^ y)
x - y = x + !y + 1
      = (x ^ y) - 2(!x & y)
      = (x & !y) - (!x & y)
      = 2(x & -y) - (x ^ y)
x ^ y = (x | y) - (x & y)
x & !y = (x | y) - y
       = x - (x & y)
!(x - y) = y - x - 1
         = !x + y
x ≡ y = (x & y) - (x | y) - 1
      = (x & y) + !(x | y)

逻辑与算数表达式中的不等式

1
2
3
4
5
6
7
(x ^ y) ≤ (x | y)
(x & y) ≤ (x ≡ y)
(x | y) ≥ max(x, y)
(x & y) ≤ min(x, y)
(x | y) ≤ x + y		若加法操作未溢出
(x | y) > x | y		若加法操作溢出
|x - y| ≤ x ^ y

绝对值函数

abs nabs
(x ^ y) - y y - (x ^ y)
(x + y) ^ y (y - x) ^ y
x - (2x & y) (2x & y) - x

若 CPU 能快速算出一个数与 ±1 的乘积，那么可以考虑用这个式子求绝对值：

1
((x >> 30) | 1) * x

两数平均值

下列公式算出两个无符号数的平均值 (x+y)/2，而且还不会溢出：

1
(x & y) + ((x ^ y) >> 1)

若是无符号整数：

1
(x | y) - ((x ^ y) >> 1)

符号 ! 优先级较高，+ - 优先级大于 << >> ，再大于 & | ^

对于两个带符号的整数，有时可能要计算向 0 取整之后的平均值。可以先算出向下取整之后的平均值，然后再修正。修正它的办法是：如果 x+y 的算术值是负奇数，则将结果再加 1。然而当且仅当上面第一式运算结果为负时（其中的无符号移位变成带符号移位），x+y 才会是负数。

1
2
t = (x & y) + ((x ^ y) >> 1)
t + ((t >> 31) & (x ^ y))

有些特例可以用更快的办法算出来。比如假设 x 和 y 都是带符号的非负数，那么只需要算出 (x+y)>>1 就能知道其平均值了。虽然两数之和可能会溢出，但是溢出的那一位仍然保留在存放加法结果的寄存器里，所以只需要执行一次无符号右移，就可以把这个溢出位挪到正确的地方，并且让空出来的那个符号位填上 0。
如果 x 和 y 都是无符号整数且 x≤y，或是 x、y 都是带符号整数且 x≤y（带符号数的比较），那么平均值就是 (y-x)>>1。这样求出来的平均值是向下取整过的，比如 -1 与 0 的平均值是 -1。

符号函数

1
2
3
4
5
sign(x) = {
	-1, x < 0,
	 0, x = 0,
	 1, x > 0
}

大部分电脑只需要 4 个指令即可实现：

1
(x >> 31) | (-x >> 31)

假若CPU没有带符号右移指令，模拟出来算式：

1
-(x >> 31) | (-x >> 31)

如果加入比较谓词，只需要 3 个指令：

1
2
(x > 0) - (x < 0)
(x >= 0) - (x <= 0)

还有一个公式：(-x >> 31) - (x >> 31)，仅 x = -2^31^ 的情况外，也能算出绝对值。

三值比较函数

1
2
3
4
5
cmp(x, y) = {
	-1, x < y,
	 0, x = y,
	 1, x > y
}
1
2
(x > y) - (x < y)
(x >= y) - (x <= y)

附录

位运算符说明

符号 说明
& 位与
| 位或
^ 、⊕ 异或
! 取反
≡ 按位等值，等同于 !(x ^ y)