倍增法：一次跳好几步，快速到达目的地

这是什么？

倍增法（Binary Lifting）是一种利用二进制思想来加速操作的方法。想象一下你在玩跳格子游戏：你一次可以跳 1 格、2 格、4 格、8 格……（都是 2 的幂次步数）。如果想去 10 格外的目标，你可以先跳 8 格，再跳 2 格，只用 2 步就完成了，而如果一格一格跳需要 10 步。生活中的例子：查字典时，你不会一页一页翻，而是先估一个大致位置，再根据页码的差值跳到大致的范围，再微调——这其实就是倍增思想的体现。

倍增法的核心是：任何一个正整数都可以拆分成若干个 2 的幂次之和（比如 10 = 8 + 2，15 = 8 + 4 + 2 + 1）。利用这个性质，我们可以用很少的步骤（O(log n) 级别）完成原本需要很多步的操作。

核心思想：二进制拆分

为什么 2 的幂次这么神奇？因为计算机里数字用二进制表示，每一位只有 0 或 1。比如 10 的二进制是 1010，从低位到高位依次表示 2^0、2^1、2^2、2^3……所以 10 = 1×2^3 + 0×2^2 + 1×2^1 + 0×2^0 = 8 + 0 + 2 + 0 = 8 + 2。每个数都可以这样拆开。

举个例子：你想计算 2^10，如果用连乘，要写 2×2×2×…共 10 次乘法。但你可以这样想：

2^1 = 2
2^2 = 4（把上一轮的 2 平方）
2^4 = 16（再把 4 平方）
2^8 = 256（再把 16 平方）

然后根据 10 的二进制（1010），把对应的幂次乘起来：2^8 × 2^2 = 256 × 4 = 1024。只用了 4 步乘法（计算平方）+ 1 次乘法（组合），远少于 10 步。

第一个应用：快速幂（计算 a 的 b 次方）

快速幂是倍增法最经典的入门例子。下面代码里，我们把指数 b 不断右移（相当于不断除以 2），同时底数 base 不断平方。当 b 的最低位是 1 时，就把当前的 base 乘到结果里。

def fast_pow(a, b):
    """计算 a 的 b 次方，b 为非负整数"""
    result = 1          # 结果初值为 1（任何数的 0 次方都是 1）
    base = a            # 底数，每一步都会平方
    while b > 0:        # 只要指数还没处理完
        if b & 1:       # 检查 b 的最低位（二进制最后一位）是否为 1
            result *= base   # 如果是，就把当前的底数乘到结果里
        base *= base    # 底数平方，为下一轮做准备（对应 2^1 -> 2^2 -> 2^4 ...）
        b >>= 1         # b 右移一位，相当于 b // 2，移掉已经处理过的最低位
    return result

print(fast_pow(2, 10))   # 输出：1024
print(fast_pow(3, 5))    # 3^5 = 243，输出：243

生活例子：你每天有 2 元零花钱，连续 10 天后你的总钱数变成 2^10 = 1024 元？不对，这是指数增长，更真实的情况是：你每天翻倍（比如第一天 2 元，第二天 4 元，第三天 8 元……），10 天后你就是 1024 元了。用连乘要算 10 次，而用快速幂只要算 4 次平方再组合一次。

第二个应用：在“跳格子”问题中快速移动

除了计算幂，倍增法还能帮我们快速找到链表或数组中某个位置往前跳 k 步的结果。想象一根数轴，上面标了位置，你想从起点跳 k 步（每次可以跳 1、2、4、8……步，但步长不能超过剩余距离）。我们可以用二进制拆分：比如 k=10，先看二进制 1010，从大到小尝试跳 8 步（如果没超过终点），再跳 2 步，正好到达。

下面是一个在数组中模拟“前进 k 步”的例子：假设有一个数组 arr，从索引 0 开始，每次可以跳 2 的幂次步（但不超过数组长度），用倍增法输出到达的目标索引。

def jump_k_steps(arr, start, k):
    """从 start 位置开始，向前移动 k 步（不能超出数组），返回目标索引"""
    n = len(arr)
    position = start
    step = 1                # 当前尝试的步长，从 2^0 = 1 开始
    # 先把 k 拆成二进制，从低位开始处理（但这里我们反向处理：从大往小）
    # 更简单的方式：用 while 循环，不断找到不超过剩余距离的最大 2 的幂
    remaining = k
    # 从最大的可能步长开始尝试（比如 2^10 = 1024，但数组长度有限）
    max_power = 1
    while max_power * 2 <= n:   # 找到数组长度内最大的 2 的幂
        max_power *= 2
    # 从大到小尝试
    while max_power > 0 and remaining > 0:
        if max_power <= remaining and position + max_power < n:
            position += max_power
            remaining -= max_power
        max_power //= 2          # 缩小到下一个 2 的幂（除以 2）
    # 如果 remaining 还有剩余（比如最后剩 1 步），也可以处理
    if remaining > 0 and position + remaining < n:
        position += remaining
    return position

# 测试
arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(jump_k_steps(arr, 0, 10))   # 从0跳10步，到10? 但数组索引9，所以只能到9，输出9

注意：这个例子更多是为了展示思想。实际中，倍增法在树结构（如求最近公共祖先 LCA）和 RMQ（区间最值）中更有用，但这里先感受一下“跳大步”的思路。

新手容易犯的错误

忘记初始化 result = 1
比如在快速幂中，如果 result 初始为 0，那乘任何数都是 0，结果永远是 0。
指数为 0 时 while 循环不执行
这是对的，因为任何数的 0 次方都是 1，而 result 初始为 1，直接返回正确结果。但注意 b 为 0 时，代码里的 while b > 0 不会进入，结果就是 1，没问题。
混淆位移运算的优先级
b & 1 要加括号吗？在 Python 中按位与 & 优先级低于比较运算符，但 b & 1 本身是数值，作为 if 条件会被解释为 True/False。实际上 if b & 1 是安全的，但为了清晰，可以写成 if (b & 1) == 1。
另外 b >>= 1 是右移赋值，注意不要写成 b >> 1 忘记赋值。
底数平方时变量的使用顺序
在 base *= base 之后，原来的 base 会被覆盖。如果后面还需要原来的 base，需要提前保存。但在快速幂中，我们正是要平方底数，所以没问题。
对负指数或非整数没有处理
快速幂通常只用于非负整数指数。如果指数是负数，需要先转为正指数再取倒数，但这个已经超出本篇范围。

完整可运行的示例代码（带输入输出）

下面是一个完整的程序，用户可以输入底数和指数，程序会输出结果，同时显示用了多少步乘法（来对比普通连乘）。

def fast_pow(a, b):
    """使用倍增法计算 a 的 b 次方"""
    result = 1          # 结果初始为 1
    base = a            # 底数
    steps = 0           # 记录乘法次数（非必要，仅用于演示）
    while b > 0:
        if b & 1:       # 检查当前最低位
            result *= base
            steps += 1  # 一次乘法
        base *= base    # 底数平方
        steps += 1      # 一次乘法
        b >>= 1         # 右移
    print(f"总共用了 {steps} 次乘法")
    return result

# 用户输入
a = int(input("请输入底数 a："))
b = int(input("请输入指数 b（非负整数）："))
print(f"{a}^{b} = {fast_pow(a, b)}")

运行示例：

请输入底数 a：2
请输入指数 b：10
总共用了 4 次乘法
2^10 = 1024

而如果用普通循环连乘，则需要 10 次乘法。对比明显。

倍增法：一次跳好几步，快速到达目的地