题目：
Implement pow(x, n).
代码：
class Solution { public: double myPow(double x, int n) { double ret = Solution::positivePow(fabs(x), abs(n)); if ( n>0 ) { if ( x<0 && n&1 ) { return -1 * ret; } } else { if ( x<0 && abs(n)&1 ) { return -1 / ret; } return 1 / ret; } return ret; } static double positivePow(double x, int n) { if ( n==0 ) return 1; if ( n==1 ) return x; double v1 = Solution::positivePow(x, n/2); double v2 = n&1 ? x : 1; return v1 * v1 * v2; } };
tips：
1. 考察binary search的思想，把计算复杂度由O(n)降低为O(logn)
2. 有个细节就是判断奇数偶数的时候，用bit判断，效率能略高一些。其实自己对计算机内部怎么执行加减乘除的原理应该是学过，但是忘记了，回头复习下。
原文：http://www.cnblogs.com/xbf9xbf/p/4538044.html