只会写递归的，应该学学非递归的。 也是O(lgn)。
比如要计算$a^b$，把b写成二进制，假设$b=11_{(10)}=1011_{(2)}=2^3+2^1+2^0$；所以$a^{11}=a^{2^3+2^1+2^0}=a^{2^3}*a^{2^3}*a^{2^0}$。
这样我也就可以把每一位的乘积项先给算出来，也就是每一次循环算出$a^{2^n}=$a^{2^{n-1}}*a^{2^{n-1}}$。如果b的第n位二进制如果为1，结果就要乘以这个项，如果为0，则不需要；
1 int power(int a, int b) { 2 int ans = 1; 3 for (; b; b >>= 1) { 4 if (b & 0x01) ans *= a; 5 a *= a; 6 } 7 return ans; 8 }
原文：http://www.cnblogs.com/linyx/p/4020227.html