利用位运算提高效率

  • 判断整数奇偶性
  • 快速取余数
  • 快速幂

判断整数奇偶性

不要用 xxx % 2 == 1 来判断整数的奇偶性了, 计算机中位运算比加减乘除快多了!

Python 中可以使用 0b..... 来表示一个二进制数.

由于二进制的表示方式, 最后一个 bit 为 1 的, 一定是奇数, 最后一个 bit 为 0 的, 一定是偶数. 问题在于如何检验一个整数的最后一个 bit?

1
2
3
odd = 0b1100
even = 0b1011
one = 0b1

答案是使用 & 与运算.

1
2
if num & 1 == 0 -> 偶数
num & 1 == 1 -> 奇数

原理

如果是一个偶数和 1 做与运算, 需要两者的二进制位都为 1 , 此位上的结果才为 1, 但是, 由于 0b1 除了最后一位以外都是 0, 因此只计算最后一位, 明显, 结果为零:

1
2
3
4
a 0b...0
b 0b...1
--------
r 0b...0 = 0

奇数和 1 的与运算也与之类似:

1
2
3
4
a 0b...1
b 0b...1
--------
r 0b...1 = 1

快速取余

位运算也可以快速地取整数除以 $2^n$ 的余数:

1
2
3
4
5
6
7
8
9
10
11
12
13
# 求 num % 2:
num & 1

# 求 num % 4:
num & 3

# 求 num % 8:
num & 7

...

# 求 num % 2**n:
num & (2**n-1)

原理

对于 2**n-1, 其二进制表示为:

1
2
2**5 = 0b100000     # 1 后面 5 个 0
X -1 = 0b 11111 # 5 个 1

一个整数, 与其进行与运算, 那么, 只有 (二进制) 最后的 n 个 bit 保持原状, 前面的 bit 全部为 0.

也就是说, 对于 % 2**n 这样的求余计算, 左操作数的后 n 个 bit 就是对应的余数.

1
2
3
4
5
6
33 % 8 == 1
num = 33, i = 7
a = 0b0100001
b = 0b 0111
-------------
r = 0b 001

对于任意一个整数, 都可以表示为以下形式:

$m,n \in N_{+}$

$$
x = o \times 2^n + o \times 2^{n-1} + \cdots + o \times 2^2 + o \times 2^1 + o \times 2^0, \quad o \in {0, 1}
$$

当这个整数除以一个 $2^m$ 时,

$$\begin{aligned}
x &= o \times 2^n + o \times 2^{n-1} + \cdots + o \times 2^2 + o \times 2^1 + o \times 2^0 \
& \div 2^m
\end{aligned}$$

由于任意 $m \le i \le n$, 都有 $2^i \% 2^m = 0$, 而剩余的 $i < m$, $2^i < 2^m$.

因此, 位数不低于 m 的, 都将被除尽, 剩余部分则为余数.

快速幂

一次传统的幂运算将会进行 n 次乘法运算. 其时间复杂度为 $O(x)$. 有一种快速幂算法, 可以将时间复杂度转化为 $O(\log_2 x)$.

用如下的递归方法, 每一步都能将指数减小一半.

$$
x^n = \bigg{
\begin{matrix}
(x^2)^{\frac{n}{2}} \
x(x^2)^{\frac{n-1}{2}}
\end{matrix}
$$

1
2
3
4
5
6
7
8
def quickPow(e, x):
result = 1
while x:
if x & 1: # 当 x 为奇数时, 将 平方 后的 e 乘入结果
result *= e
e *= e # 底数 平方
x >>= 1 # 指数右移一位, 无论最后一位是 0 或 1, 都将被舍掉
return result
1
2
3
4
5
6
7
3**0b1101 == 3**(0b0 + 0b1 + 0b00 + 0b100 + 0b1000)
== 3**0b0 * 3**0b1 * 3**0b00 * 3**0b100 * 3**0b1000
# 一次幂运算可以如上展开
== (1 * 3**0b1) * 9**0b0 * 9**0b10 * 9**0b100
== (1 * 3**0b1 * 9**0b0) * 81**0b1 * 81**0b10
== (1 * 3**0b1 * 9**0b0 * 81**0b1) * 6561**0b1
== result

可以看到, 将指数按二进制位拆分, 然后依次对其进行: “指数减半, 底数平方” 的操作, 直到指数只有一 bit 为止. 当在其中遇到指数为 1 的情况时, 说明该次计算已经化到最简, 因此, 将其乘入结果(用括号()表示).


对普通幂与快速幂测试:

底数: 2, 指数: 8,16,32,64,128,256 重复次数: 10000

1
2
3
4
5
def pow(e, x):
result = 1
for i in range(x):
result *= e
return result
1
2
3
4
5
6
7
8
def quickPow(e, x):
result = 1
while x:
if x & 1: # 当 x 为奇数时, 将 平方 后的 e 乘入结果
result *= e
e *= e # 底数 平方
x >>= 1 # 指数右移一位, 无论最后一位是 0 或 1, 都将被舍掉
return result
指数普通幂快速幂
8865ns828ns
161250ns924ns
322010ns1130ns
644180ns1430ns
1288510ns1640ns
25617900ns1810ns

当指数不断翻倍时, 快速幂耗时线性增加, 而普通幂却是指数型增长. 孰强孰弱, 一目了然.