leetcode Pow(x, n)

gistfile1.md

###leetcode Pow(x, n)

####思路

• 尽量减少计算乘法的次数
  • 如果n是奇数，则 pow(x, n) = x * pow(x, n - 1)
  • 如果n是偶数，则 pow(x, n) = pow(x, n >> 1) * pow(x, n >> 1)

####NOTE

• n < 0时
• n = 0时
• n = 1时

#####java code

public class Solution {
    public double pow(double x, int n) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if (0 == n) return 1;
      if (1 == n) return x;
		boolean negative = n < 0;
		n = negative ? -n : n;

		double val = 0;
		if ((n & 1) == 1) {
			val = x * pow(x, n - 1);
		} else {
			double tmp = pow(x, n >> 1);
			val = tmp * tmp;
		}
		if (negative) return 1 / val;
		return val;
    }
}