如何用C语言高效实现快速幂算法？

本文共计337个文字，预计阅读时间需要2分钟。

引言：快速求幂是指快速求得a的b次方的值。求a^b，最朴素的想法是不间断地进行b次乘法，但实际需要的是b次乘法运算吗？

分析：假设要计算2^32，当求2^16次方之后，可以直接得到2^32=2^16*2^16=2^1=2。这说明在某些情况下，可以通过部分计算得到最终结果。

引言

所谓快速幂是指快速求得a的b次方的方法。求a^b，最朴素的想法便是不断进行b次累乘，但真的需要进行b次乘法运算吗？

分析

假如要计算2^{32，当求得2}16次方之后，可以直接对2^{16进行平方得到2}32，并不需要在2^16基础上再进行16次累乘。

相应地，求2^16只需对28求平方即可。同理，求2^{8，只需对2}4平方……以此类推。

例如求3^29等价于求\(3^1 * 3^4 * 3^8 * 3^{16}\)

那么1，4，8，16是怎么算出来的呢？

29的二进制表示为11101

所以$29=2⁴⁺²3+2²⁺²0=16+8+4+1 $

这样就确定了3的哪些次幂是要进行累乘的。

代码

#include <cstdio> using namespace std; // 求快速幂 int QuickPower(int x,int n){ int answer = 1; while (n != 0) { if (n % 2 == 1) { answer *= x; } n /= 2; x *= x; } return answer; } int main(){ int a,b; printf("%d\n", QuickPower(a, b)); return 0; }