50. Pow(x, n)

题意：

求x的n次方。

思路：平方加速

萌新肯定就直接转换成加法了，不用想这样肯定是超时的。
若加快运行速度，合适的方法就是在适当的时候平方。

先说一下范围限制的问题，int在32位系统下的范围是 [−2³², 2³¹ − 1]，也就是说当n为负数不能简单的n=-n,x=1/x，因为当n为−2³²时会超界。正确的方法是转化成1/x的-n+1次方再乘一个1/x，也就是说求xⁿ等价于求 xⁿ * x^-1。

首先写出来递归形式的代码，代码简洁但会比较慢。

double myPow(double x, int n) {
	if (n < 0)
		return 1 / x*myPow(1 / x, -n - 1);
	if (n == 0)
		return 1;
	if (n == 1)
		return x;

	double half = myPow(x, n / 2);
	if (n % 2)
		return x*half*half;
	else
		return half*half;
}

然后转化成非递归模式，使用一个stack存每次除以2的结果，
比如19 -> 9 -> 4 -> 2 。
需要记录每次的结果而并不是简单的得到次数的原因是 每次有奇数就说明少乘了一份，需要多计算一次*x。
切分的时候n>=2的话要继续分，n==1的时候直接返回就可以了。

double myPow(double x, int n) {
	if (n == 0)
		return 1;
	if (n < 0)
		return myPow(1 / x, -(n + 1)) / x;

	stack<int> s;
	for (; n != 1; n /= 2)
		s.push(n);
	double res = x;

	while (!s.empty()) {
		res *= res;
		if (s.top() % 2)
			res *= x;
		s.pop();
	}
	return res;
}