[ACM]反复平方法的两种写法

一直以来对反复平方法都是知道个大概意思，但是一直都处于混淆的状态，今天总结一下。

网上通常看到的代码是这个样子的：

 1 int pow(int a, int b) {
 2     int result = 1;
 3     int r = a;
 4     while (b) {
 5         if (b & 1) {
 6             result *= r;
 7         }
 8         r *= r;
 9         b /= 2;
10     }
11     return result;
12 }

假设b为1011的话，列出来b运算过的部分 result r的结果是：

b运算过的部分 result r

0 1 a

1 a a^2

11 a*a^2 a^4

011 a*a^2 a^8

1011 (a*a^2)*a^8 a^16

第二种实现是《算法导论》的实现，代码是这个样子的：

 1 int pow(int a, int b) {
 2     int result = 1;
 3     for (int i = 31; i>=0; i--) {
 4         result *= result;
 5         if (b & 1<<i) {
 6             result *= a;
 7         }
 8     }
 9     return result;
10 }

这个就比较好懂了，同样以b=1011为例，result的值依次是a^1 , a^10 , a^101 , a^1011。可以看出来，这个才是真正“原汁原味的”反复平方法