牛客网剑指offer第12题——数值的整数次方

题目：

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

初次拿到这个题目，我们当然知道采用累乘的方法。但是傻子都知道这种做法，时间复杂度自然是O（n）级别的。有没有更为简单的做法呢？

有的，那就是快速幂。

快速幂

求 x 的 n 次方
当然，这道题你也可以采用 n 次循环让 n 个 x 相乘，不过，这样的做法毫无意义，因为估计小学生也会做。

不过这道题如果知道了思路，还是挺简单，我举个例子吧，例如我们要求 2^8。

1、首先，我们可以通过 2 * 2 = 4 得到 2^2

2、接着，我们利用刚才的结果，让 4 * 4 = 16 得出 2^4

3、接着，同样的道理，让 16 * 16 = 256 得出 2^8

通过这种方法，只需要三次相乘即可得出，也就是说，我们可以在 O(logn) 的时间复杂度求出 x 的 n 次方。这种方法的思想，我们也称之为快速幂思想，和二分查找的思想有点类型，每次都进行翻倍或者缩小一半。

这个时候有人可以能会问，如果 n = 8 或者 n = 16 ，由于 n 是 2 的幂次方，所以可以按照你上面的方法做，那如果 n = 12 呢？

其实道理是一样的，我们可以对 12 进行拆分啊，把 12 拆分成 12 = 4 + 8 就可以了。然后就有 2^12 = 2^4 * 2^8。

那如果 n = 13 呢，也是一样的，拆分成 13 = 1 + 4 + 8，即 2^13 = 2^1 * 2^4 * 2^8。

也就是说，任何整数，都可以把它拆分成若干个 2 的幂次方进行相加。
这也是一种很常见的思想，我当时也想到了这种方法，但终究无法写出代码，究其原因是对于位运算的不熟练导致的。

快速幂额核心思想是什么：任意整数指数表示成2的幂次的和，而快速幂算法中我们可以通过对整数的移位表征这种关系。

比如9 = 2³+2⁰，因此，当我们要求5⁹的的时候，我们会想到5⁹=5^（8+1）=5⁸×5¹。但在实际中，又该怎么表示这种关系呢。这个时候我们就要用到位运算了。为何?9 = 1001(二进制)。因此，我们可以通过对指数的二进制处理。来进行操作。

来看代码：

 1 int fastPower(int base, int exponent) {
 2     int sum = 1;
 3     while (exponent != 0) {
 4         if ((exponent & 1) != 0) {
 5             sum *= base;
 6         }
 7         exponent = expnonent >> 1;  // 对指数进行移位
 8         base *= base;               // 让base的次幂以2的倍数增长
 9     }
10     return sum;
11 }

代码十分的简洁。我们可以看到的是。第7行的代码完成了对指数的移位运算。而这个移位运算的作用，就是将2的整数次幂给剥离出来。还需要注意的是&是按位与的意思。因此num&1是判断num的二进制形式的最后一位是否为1.

以上述代码为例子，求59，看会发生什么？

9 = 1001（二进制）-> （1001&1） == 1->sum = 1*5=5;

1001>>1 = 100；base = 5*5 (25)

下一次循环:

100&1 == 0->sum值不变；

100>>1 = 10；base = (5*5)*（5*5）;

下一次循环：

10&1 == 0->sum值不变；

10>>1 = 1；base = ((5*5)*（5*5）)*((5*5)*（5*5）);

下一次循环:

1&1 = 1->sum = sum*base = 5*((5*5)*（5*5）)*((5*5)*（5*5）) = 5¹*5⁸=5⁹

我们可以看到的是9 = 1001 = 2^3+2^1。通过移位运算表示出来了。

因此，此题最终代码为：

 1 class Solution {
 2 public:
 3     double Power(double base, int exponent) {
 4     double sum =1.0;
 5     unsigned int abs_exponent =abs(exponent);
 6     while(abs_exponent> 0)
 7     {
 8         if(abs_exponent&1 != 0)
 9         {
10             sum *=base;
11         }
12         abs_exponent = abs_exponent>>1;
13         base*=base;
14     }
15         if(exponent>=0)
16             return sum;
17         else
18             return 1.0/sum;
19     }
20 };