剑指Offer第12题：数值的整数次方

发表于 更新于 分类于

题目：给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。保证base和exponent不同时为0。

解题思路：最直接的想法就是将base乘以exponent次，然而这种方法显然存在重复计算。考虑二进制数的表示形式，例如十进制下的13对应的二进制为1101，表示$13=1\times 2^0+0\times 2^1 + 1\times 2^2 + 1\times 2^3$，现在需要计算k的13次方，即$k^{13}=k^{1 + 4 + 8}=k^1\times k^4\times k^8$，为13对应二进制位上为1的$k^n$相乘，n为二进制1所在位置的十进制值。下表可表示此过程：

1 1 0 1
$k^8$ $k^4$ $k^2$ $k^1$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
double Power(double base, int exponent) {
    if (exponent<0) { //先对负指数做转换
        exponent *= -1;
        base = 1/base;
    }
    double res = 1;
    while (exponent > 0) {
        if (exponent % 2 == 1) { //对应二进制位上为1时，乘上先前的结果
            res *= base;
        }
        base *= base; //计算每个二进制位上的基数值
        exponent >>= 1; //计算完一次二进制位后，右移一位
    }
    return res;
}