LeetCode | Pow(x, n)

题目

Implement pow(x, n).

分析

分治法（解法1）和一种比较巧的方法（解法2）

解法1

public class Pow {
	public double pow(double x, int n) {
		if (n == 0) {
			return 1;
		} else if (n > 0) {
			if (n == 1) {
				return x;
			}
			double halfReuslt = pow(x, n >> 1);
			double result = halfReuslt * halfReuslt * pow(x, n & 0x1);
			return result;
		} else {
			if (n == Integer.MIN_VALUE) {
				return 1 / (pow(x, Integer.MAX_VALUE) * x);
			}
			return 1 / pow(x, -n);
		}
	}
}

public class Pow {
	public double pow(double x, int n) {
		if (n == 0) {
			return 1.;
		} else if (n > 0) {
			double result = 1.;
			for (; n > 0; n >>= 1) {
				if ((n & 1) > 0) {
					result *= x;
				}
				x *= x;
			}
			return result;
		} else {
			if (n == Integer.MIN_VALUE) {
				return 1. / (pow(x, Integer.MAX_VALUE) * x);
			}
			return 1. / pow(x, -n);
		}
	}
}