数值的整数次方.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

这里