1. 前情

在 第二章 幂运算 中，我们知道了如何利用递归快速的求解幂运算。
虽然简单，但是效率不高，因为函数调用的代价非常昂贵，如果将递归改成迭代循环，则会进一步的提升效率。

2. 代码实现

自己写的

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int main()
  4. {
  5.     int x=2;
  6.     int n=10;
  7.     int arr[10]={0};//用于存储n每一次/2变换之前是奇数还是偶数
  8.     int i=1;
  9.     while(n>1){//当n=1时，循环结束
  10.         arr[i++]=n%2;
  11.         n/=2;
  12.     }
  13.     int res=x;
  14.     for(int j=i-1;j>0;j--){
  15.         if(arr[j]==1){
  16.             res=res*res*x;
  17.         }else if(arr[j]==0){
  18.             res=res*res;
  19.         }
  20.     }
  21.     cout<<"res="<<res<<endl;
  22. }

优化后的

  1. //循环求幂显现
  2. double Pow2(double x, unsigned int n)
  3. {
  4.     double result = 1;
  5.     while (n)
  6.     {
  7.         if (n & 1)        // 等价于 if (n % 2 != 0)
  8.             result *= x;
  9.         n >>= 1;
  10.         x *= x;
  11.     }
  12.     return result;
  13. }

这个代码将上文代码中的两个循环捏合到一起，并抛弃数组，用位运算来取二进制的最后一位，进一步的提升了效率。
注意：用位运算来取二进制的最后一位 和上文代码中数组的标志位是一一对应的（数组末尾的数对应开始位运算的倒数第二位）。

3. 参考

数据结构与算法分析 2.23 不用递归，写出快速求幂的程序

4. 习题 2.17

根据上述分析，在实际代码中（优化后的），N=0，乘法次数为0，N=1，乘法次数为2.
若b（N）为N中二进制表示中数字1的个数，在代码中乘法次数为：
logN（向上取整）+b（N）。
答案中，因为少算了 result 从1到n的过程（1次）和少算了while循环中 x的最后一次自乘（准确来说没有必要自乘，但是自乘保证了程序的一致性），所以答案是：
image.png