Pow(x, n)（50）

题目

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

示例

输入: 2.00000, 10 输出: 1024.00000

输入: 2.10000, 3 输出: 9.26100

输入: 2.00000, -2 输出: 0.25000

说明

• -100.0 < x < 100.0
• n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

算法

快速幂算法（递归）

使用分治算法的思想，例如求x^64时，我们不需要将x连乘64次，而是x -> x^2 -> x^4 -> x^8 -> x^16 -> x^32 -> x^64每次对上次的结果平方，这样计算6次就得到了结果

如果最后要求的是x^77时，我们可以将其转化为x -> x^2 -> x^4 -> x^9 -> x^19 -> x^38 -> x^77，我们可以在其中某一项平方后再乘x，比如x^38 * x^38 * x === x^77

如果我们倒推整个式子，将会更加容易判断是否需要+1，所以我们递归的时候也从后向前进行递归：

• 递归结束条件是当前的n为0时返回1
• 传入下一轮递归的是幂运算底数x和指数/2，指数/2作为下一轮判断是否需要再乘x并控制总迭代次数
• 每一轮返回结果根据当前的n能不能被2整除，决定返回上一轮的值是平方还是平方乘x

再myPow()中调用递归函数mul()的时候，因为n可能为负，所以我们需要进行正负判断

export const myPow_2 = (x, n) => {
	return n >= 0 ? mul(x, n) : 1 / mul(x, -n);
};
const mul =  (x, n) => {
	if (n === 0) return 1;
	let y = mul(x, ~~(n / 2));
	return n % 2 === 0 ? y * y : y * y * x;
};

快速幂算法（迭代）

以pow(2, 77)为例子，我们按照之前的分析可知x -> x^2 -> x^4 -> x^9 -> x^19 -> x^38 -> x^77，这个过程中x^4 -> x^9、x^9 -> x^19、x^38 -> x^77这三个过程需要乘以额外的x，其余的x都是第一步中的x不断平方后的结果

• 对于第一个x，我们经过了6次平方，这个x为结果贡献了2^6个x
• 对于x^4 -> x^9中，我们额外乘了一个x，这个x在之后的运算中被平方了3次，这个x为结果贡献了2^3个x
• 对于x^9 -> x^19中，我们额外乘了一个x，这个x在之后的运算中被平方了2次，这个x为结果贡献了2^2个x
• 对于x^38 -> x^77中，我们额外乘了一个x，这个x为结果贡献了1个x

所以我们指数77就等于2^6 + 2^3 + 2^2 + 2^0，而这里的运算恰好可以转换为(1001101)2，即77的二进制表达，每一个加数对应二进制的一个1

所以我们将整数拆分成二进制的表达式，就可得迭代的规律：

x^77 => x^64 * x^8 * x^4 * x^1 => x^(64 + 8 + 4 + 1) => x^(2^6 + 2^3 + 2^2 + 2^0)

所以我们在迭代中不断地平方x，从右往左得遇到二进制位为1时，将累计的x_contribute乘入结果ans

export const myPow = (x, n) => {
	return n >= 0 ? mul(x, n) : 1 / mul(x, -n);
};
const mul = (x, n) => {
	let ans = 1;
	let x_contribute = x;
	while (n > 0) {
		if (n % 2 === 1) ans *= x_contribute;
		x_contribute *= x_contribute;
		n = ~~(n / 2);
	}
	return ans;
};