算法与数据结构：位运算与快速幂

位运算

在计算机的世界中，一切数字都是二进制的。类比于现实世界中我们所使用的十进制，二进制即为「逢二进一」的运算体系。

我们以 B、D 来分别标记二进制与十进制，例如 10D 表示十进制中的 10，而 10B 则表示二进制中的 10。

回顾十进制，
$$\begin{gathered} 10D=1\times 10^1+0\times 10^0=10 \\ 123D=1\times 10^2+2\times 10^1+3\times 10^0=123 \end{gathered}$$

类比十进制，进一步理解二进制：
$$\begin{gathered} 10B=1\times 2^1+0\times 2^0=2D \\ 123B=1\times 2^2+2\times 2^1+3\times 2^0=11D \end{gathered}$$

由此我们可以发现，十进制就是「逢十进一」，而二进制就是「逢二进一」。

在计算机的运算过程中，所有的数字都是用「二进制」表示的，其中数字的每一位称为一个 bit，其取值要么为 0，要么为 1。

「位运算」是「二进制」所特有的运算，共分为 6 类，如下表所示：

运算符	名称	规则
&	与	两个位均为1，结果为1
|	或	两个位均为0，结果为0
^	异或	两个位相同则为0，不同则为1
~	取反	0变1，1变0
<<	左移	二进制下所有位同时向左移动，低位用0填充，高位越界后舍弃
>>	右移	二进制下所有位同时向右移动，无符号数高位补0，有符号数视编译器而定

我们以 1011B、0101B 举例（均为无符号数）：

• 1011B & 0101B = 0001B
• 1011B | 0101B = 1111B
• 1011B ^ 0101B = 1110B
• ~1011B = 0100B
• 1011B << 2 = 101100B
• 1011B >> 2 = 10B

想要彻底掌握位运算，还需了解原码、反码、补码等知识，但由于本文重点并不在此，因此不再详细展开。

快速幂

接下来开始介绍「快速幂」算法，该算法常用于快速指数运算。

举个例子，如果想要计算 $2^{31}$ 的具体数值，最少需要计算多少次可以完成？

一个比较显然的答案是从 1 开始连乘 31 个 2，这样肯定可以得到准确的答案，但是否有更快的方法？

答案显然是「有」，如果我们用二进制来表示 31，则可以得到：
$$31D=11111B=1\times 2^4+1\times 2^3+1\times 2^2+1\times 2^1+1\times 2^0=31D$$

由此我们可以将 $2^{31}$ 进行转化，得到：
$$2^{31}=2^{1+2+4+8+16}=2^1\times 2^2\times 2^4\times 2^8\times 2^{16}$$

因此我们只需要求出 $2^1,2^2,2^4,2^8,2^{16}$ ，再将它们依次相乘，就可以得到$2^{31}$ 。

我们从 1 开始只需要计算 5 次即可求出 $2^{16}$ 。再将这几个数字依次乘起来，就得到了 $2^{31}$ 。

这种通过将指数转化为二进制，并以此来加快幂运算的方法就是快速幂。当计算
$a^x$ （ a 为任意实数）时，快速幂方法可以将原来的 $O(x)$ 时间复杂度降低为
$O(log(x))$ ，从而大大加快指数运算。

实现该算法所需代码并不长，大家可以手动实现，也可以参考下述代码：

// 计算 a ^ b
int poww (int a, int b) {int base = a, ans = 1;while (b) {if (b & 1) ans *= base;base *= base;b >>= 1;}return ans;
}

# 快速幂算法
def poww(a, b):base = a;ans = 1;while (b):print("b:", b)if ( b & 1):ans *= base;base *= base;b >>= 1;print(ans);return ans;poww(2, 14);b: 14
b: 7
b: 3
b: 1
16384