数值的整数次方.md

数值的整数次方

知识点：代码的完整性

题目描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

解题思路

这是典型的快速求幂算法的题，举个例子：

$3 ^{ 999}$ = 3 * 3 * 3 * … * 3

直接乘要做998次乘法，复杂度为$O(n)$.

但事实上可以这样做，先求出2^k次幂：

$3 ^ 2$ = 3 * 3 $3 ^ 4$ = $3 ^ 2$* $3 ^ 2$ $3 ^ 8$ = $3 ^ 4$* $3 ^ 4$ $3 ^{16}$ = $3 ^ 8$ * $3 ^ 8$ $3 ^ {32}$ = $3 ^{16}$ * $3 ^{16}$ $3 ^{64}$ = $3 ^ {32} $* $3 ^ {32}$ $3 ^{128}$ = $3 ^ {64}$ * $3 ^ {64}$ $3 ^ {256}$ = $3 ^ {128}$ * $3 ^ {128}$ $3 ^ {512}$ = $3 ^ {256}$ * $3 ^ {256}$

再相乘：

$3 ^ {999}$ = $3 ^ {(512 + 256 + 128 + 64 + 32 + 4 + 2 + 1)}$ =$ 3 ^ {512}* 3 ^ {256} * 3 ^ {128} * 3 ^ {64}* 3 ^ {32} * 3 ^ 4 * 3 ^ 2 * 3$

这样只要做16次乘法,复杂度为$O(logn)​$,即使加上一些辅助的存储和运算，也比直接乘高效得多（尤其如果这里底数是成百上千位的大数字的话）。 我们发现，把999转为2进制数：1111100111，其各位就是要乘的数.

所以我们只需利用exponent的二进制位即可，同时需要考虑exponent和base的特殊情况，比如0 、正、负等。

代码

核心代码：

sum = 1.0
tmp = base
while (exponent > 0):
    if exponent & 1 == 1:
    sum *= tmp
    tmp *= tmp
    exponent = exponent >> 1

这里