快速幂算法详解（用Rust轻松实现高效幂运算）

Rust 实现快速幂

下面我们用 Rust 来实现快速幂。Rust 是一种内存安全、高性能的系统编程语言，非常适合编写高效算法。

方法一：递归实现

fn fast_pow_recursive(base: i64, exp: u32) -> i64 {    if exp == 0 {        return 1;    }    let half = fast_pow_recursive(base, exp / 2);    if exp % 2 == 0 {        half * half    } else {        base * half * half    }}

这个函数接受底数 base 和指数 exp，返回 base^exp。注意我们使用 u32 作为指数类型，避免负指数带来的复杂性（负指数通常涉及浮点数）。

方法二：迭代实现（更高效，避免栈溢出）

递归虽然直观，但当指数很大时可能导致栈溢出。因此，更推荐使用迭代方式实现快速幂：

fn fast_pow_iterative(mut base: i64, mut exp: u32) -> i64 {    let mut result = 1;    while exp > 0 {        // 如果指数是奇数，把当前 base 乘到结果中        if exp % 2 == 1 {            result *= base;        }        // base 平方，指数减半        base *= base;        exp /= 2;    }    result}

这个版本使用 while 循环，不断将指数右移（相当于除以2），同时根据指数的最低位是否为1来决定是否将当前 base 乘入结果。这实际上是在模拟指数的二进制表示。

为什么快速幂这么快？

举个例子：计算 3^13。

13 的二进制是 1101，即 8 + 4 + 0 + 1，所以：

3^13 = 3^8 × 3^4 × 3^1

我们只需要计算 3^1, 3^2, 3^4, 3^8（每次平方），然后根据二进制位选择相乘即可。总共只需约 log₂(13) ≈ 4 步，而不是 13 次乘法！

完整示例与测试

fn main() {    println!("{}", fast_pow_iterative(2, 10)); // 输出 1024    println!("{}", fast_pow_iterative(3, 13)); // 输出 1594323    println!("{}", fast_pow_iterative(5, 0));  // 输出 1}// 使用上面定义的 fast_pow_iterative 函数

注意事项

• 整数溢出：Rust 默认不进行溢出检查（release 模式），如果结果可能很大，建议使用 i128 或处理溢出（如取模）。
• 取模快速幂：在算法竞赛中，常要求结果对某个数（如 10⁹+7）取模。只需在每次乘法后加 % MOD 即可。

总结

快速幂算法是 Rust编程 和算法学习中的基础技巧，它体现了分治与二进制思想的巧妙结合。通过本文，你已经掌握了如何用 Rust 实现高效幂运算，无论是 快速幂算法 的递归还是迭代写法，都能轻松应对大指数计算。

记住，算法优化不仅能提升程序性能，在面试和竞赛中也是加分项。现在就动手试试吧！

关键词：Rust快速幂, 快速幂算法, Rust编程, 算法优化