题目：实现函数double Power(double base, int exponent)，求base的exponent次方。不需要考虑溢出。
分析：这是一道看起来很简单的问题。可能有不少的人在看到题目后30秒写出如下的代码：
1 double Power(double base, int exponent)
2 {
3 double result = 1.0;
4 for(int i = 1; i <= exponent; ++i)
5 result *= base;
6
7 return result;
8 }
上述代码至少有一个问题：由于输入的exponent是个int型的数值，因此可能为正数，也可能是负数。上述代码只考虑了exponent为正数的情况。
接下来，我们把代码改成：
1 bool g_InvalidInput = false;
2
3 double Power(double base, int exponent)
4 {
5 g_InvalidInput = false;
6
7 if(IsZero(base) && exponent < 0)
8 {
9 g_InvalidInput = true;
10 return 0.0;
11 }
12
13 unsigned int unsignedExponent = static_cast<unsigned int>(exponent);
14 if(exponent < 0)
15 unsignedExponent = static_cast<unsigned int>(-exponent);
16
17 double result = PowerWithUnsignedExponent(base, unsignedExponent);
18 if(exponent < 0)
19 result = 1.0 / result;
20
21 return result;
22 }
23
24 double PowerWithUnsignedExponent(double base, unsigned int exponent)
25 {
26 double result = 1.0;
27 for(int i = 1; i <= exponent; ++i)
28 result *= base;
29
30 return result;
31 }
32
上述代码较之前的代码有了明显的改进，主要体现在：首先它考虑了exponent为负数的情况。其次它还特殊处理了当底数base为0而指数exponent为负数的情况。如果没有特殊处理，就有可能出现除数为0的情况。这里是用一个全局变量来表示无效输入。关于不同方法来表示输入无效的讨论，详见本系列第17题。
最后需要指出的是：由于0^0次方在数学上是没有意义的，因此无论是输入0还是1都是可以接受的，但需要在文档中说明清楚。
这次的代码在逻辑上看起来已经是很严密了，那是不是意味了就没有进一步改进的空间了呢？接下来我们来讨论一下它的性能：
如果我们输入的指数exponent为32，按照前面的算法，我们在函数PowerWithUnsignedExponent中的循环中至少需要做乘法31次。但我们可以换一种思路考虑：我们要求出一个数字的32次方，如果我们已经知道了它的16次方，那么只要在16次方的基础上再平方一次就可以了。而16次方是8次方的平方。这样以此类推，我们求32次方只需要做5次乘法：求平方，在平方的基础上求4次方，在4次方的基础上平方求8次方，在8次方的基础上求16次方，最后在16次方的基础上求32次方。
32刚好是2的整数次方。如果不巧输入的指数exponent不是2的整数次方，我们又该怎么办呢？我们换个数字6来分析，6就不是2的整数次方。但我们注意到6是等于2+4，因此我们可以把一个数的6次方表示为该数的平方乘以它的4次方。于是，求一个数的6次方需要3次乘法：第一次求平方，第二次在平方的基础上求4次方，最后一次把平方的结果和4次方的结果相乘。
现在把上面的思路总结一下：把指数分解了一个或若干个2的整数次方。我们可以用连续平方的方法得到以2的整数次方为指数的值，接下来再把每个前面得到的值相乘就得到了最后的结果。
到目前为止，我们还剩下一个问题：如何将指数分解为一个或若干个2的整数次方。我们把指数表示为二进制数再来分析。比如6的二进制表示为110，在它的第2位和第3位为1，因此6=2^(2-1)+2^(3-1) 。也就是说只要它的第n位为1，我们就加上2的n-1次方。
最后，我们根据上面的思路，重写函数PowerWithUnsignedExponent：
1 double PowerWithUnsignedExponent(double base, unsigned int exponent)
2 {
3 std::bitset<32> bits(exponent);
4 if(bits.none())
5 return 1.0;
6
7 int numberOf1 = bits.count();
8 double multiplication[32];
9 for(int i = 0; i < 32; ++i)
10 {
11 multiplication[i] = 1.0;
12 }
13
14 // if the i-th bit in exponent is 1,
15 // the i-th number in array multiplication is base ^ (2 ^ n)
16 int count = 0;
17 double power = 1.0;
18 for(int i = 0; i < 32 && count < numberOf1; ++i)
19 {
20 if(i == 0)
21 power = base;
22 else
23 power = power * power;
24
25 if(bits.at(i))
26 {
27 multiplication[i] = power;
28 ++count;
29 }
30 }
31
32 power = 1.0;
33 for(int i = 0; i < 32; ++i)
34 {
35 if(bits.at(i))
36 power *= multiplication[i];
37 }
38
39 return power;
40 }
41
在上述代码中，我们用C++的标准函数库中bitset把整数表示为它的二进制，增大代码的可读性。如果exponent的第i位为1，那么在数组multiplication的第i个数字中保存以base为底数，以2的i次方为指数的值。最后，我们再把所以位为1在数组中的对应的值相乘得到最后的结果。
上面的代码需要我们根据base的二进制表达的每一位来确定是不是需要做乘法。对二进制的操作很多人都不是很熟悉，因此编码可能觉得有些难度。我们可以换一种思路考虑：我们要求出一个数字的32次方，如果我们已经知道了它的16次方，那么只要在16次方的基础上再平方一次就可以了。而16次方是8次方的平方。这样以此类推，我们求32次方只需要做5次乘法：先求平方，在平方的基础上求4次方，在4次方的基础上平方求8次方，在8次方的基础上求16次方，最后在16次方的基础上求32次方。
也就是说，我们可以用如下公式求a的n次方：
这个公式很容易就能用递归来实现。新的PowerWithUnsignedExponent代码如下：
1 double PowerWithUnsignedExponent(double base, unsigned int exponent)
2 {
3 if(exponent == 0)
4 return 1;
5 if(exponent == 1)
6 return base;
7
8 double result = PowerWithUnsignedExponent(base, exponent >> 1);
9 result *= result;
10 if(exponent & 0x1 == 1)
11 result *= base;
12
13 return result;
14 }
以上转自何海涛博客
关于第二种方法，可以采用《编程之美》中2.9节关于裴波那契数列的lg(n)方法，大概思路如下
1 double result = 1.0;
2 double tmp = base;
3 int n = exponent*-1;
4 for(;n;n>>=1)
5 {
6 if(n&1)
7 result *= tmp;
8 tmp *= tmp;
9
10 }
不过注意，因为int的范围是-32768～32767，如果exponent=-32768，那么取反后，n还是有溢出风险的。