利用位运算提高效率

  • 判断整数奇偶性
  • 快速取余数
  • 快速幂
  • 交换两值

位运算的运算规律

位运算分别有 & 与, | 或, ~ 非, ^ 异或 四种.

与运算

两者同时为 1 才为 1.

左操作数 右操作数 结果
1 1 1
0 1 0
1 0 0
0 0 0

或运算

两者一者为 1 就为 1.

左操作数 右操作数 结果
1 1 1
0 1 1
1 0 1
0 0 0

非运算

反过来.

异或运算

相同为 0, 不同为 1

左操作数 右操作数 结果
1 1 0
0 1 1
1 0 1
0 0 0

运算律

交换律

1
2
3
a & b == b & a;
a | b == b | a;
a ^ b == b ^ a;

自运算

1
2
3
a & a == a;
a | a == a;
a ^ a == 0;

结合律

1
2
3
a & b | b == b;
a | b & a == a;
a ^ b ^ a == a ^ a ^ b == 0 ^ b == b;

判断整数奇偶性

不要用 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 = (x^2)^{\frac{n}{2}} \; \text{or} \; x(x^2)^{\frac{n-1}{2}} $$

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
指数 普通幂 快速幂
8 865ns 828ns
16 1250ns 924ns
32 2010ns 1130ns
64 4180ns 1430ns
128 8510ns 1640ns
256 17900ns 1810ns

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

无需中间变量即可交换两数的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>

int main(int argc, char* argv[])
{
int a, b;
while(scanf("%d %d", &a, &b) != EOF) {

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

printf("%d %d", a, b);
}
return 0;
}

原理

异或运算法则: 相同 bit 为 0, 不同 bit 为 1.

记最初的两个值为 a, b, 并分别用 x, y 作为变量名:

第一次异或运算:

1
2
x   = a ^ b;
y = b;

第二次异或运算:

1
2
3
x   = a ^ b;
y = (a ^ b) ^ b;
= a;

第三次异或运算:

1
2
3
x   = (a ^ b) ^ a;
= b;
y = a;