当前位置：首页 > news >正文

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

news 来源：原创 2025/7/18 4:39:18

文章目录

- - - 位运算
    - 快速幂

位运算

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

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

回顾十进制，
$1\times 10^1 + 0\times 10^0 = 10 \\ 123D = 1\times 10^2 + 2\times 10^1 + 3\times 10^0 = 123$

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

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

在计算机的运算过程中，所有的数字都是用「二进制」表示的，其中数字的每一位称为一个 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，则可以得到：
$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 (l o g (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

文章目录

位运算

快速幂

相关文章：