实现Pow(x, n)
累乘当然可以，但效率太低了。网上搜的很多用的都是分治的思想，递归实现，感觉有点复杂。
分析下吧
n = n1 * 2^0 + n2 * 2^1 + n3 * 2^2 + ...
x^n = x^(n1 * 2^0 + n2 * 2^1 + n3 * 2^2 + ...) = (x^(2^0))^n0 * (x^(2^1))^n1 * ...
也许这么看着很复杂，其实就是把n分解成二进制数就很清晰了，为1的位才相乘，为0的跳过，另外还要处理次幂为负的情况，看了代码就清晰~
1 class Solution { 2 public: 3 double pow(double x, int n) { 4 double ret = 1; 5 if (n < 0) { 6 x = 1/x; 7 n = -n; 8 } 9 while (n > 0) { 10 if (n & 1) 11 ret *= x; 12 x = x * x; 13 n >>= 1; 14 } 15 return ret; 16 } 17 };
Leetcode OJ: Pow(x, n),布布扣,bubuko.com
原文：http://www.cnblogs.com/flowerkzj/p/3647776.html