算法通关村第十三关——幂运算问题解析

前言

幂运算为常见的数学运算，形式为 $a^b$ ，其中a为底数，b为指数，

力扣中，幂运算相关的问题主要是判断一个数是不是特定正整数的整数次幂，以及快速幂的处理。

1.求2的幂

力扣231题，给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true；否则，返回 false 。

分析：第一种方法是我们可以用通过逐渐缩小n值来判断是否是2的幂次方，只需要循环用除的方法就可以了，还需要判断一下n是否是正整数，如果不是就直接返回false。第二种方法是位运算，如果n是2的幂次方，那么n的二进制表示就只有一个1，如果存在非负整数 k 使得 $n=2^k$，则 n 的二进制表示为 1 后面跟 k 个0，比如n=4，其二进制表示为 $(0100{)}_2$,n-1也就是3的二进制表示则为 $(0011{)}_2$ ，使用位运算n & (n - 1)如果结果为0就说明n是2的幂次方，否则不是。

代码如下：

/**
 * 采用除法
 * @param n {number}
 * @return {boolean}
 * */
function isPowerOfTwo(n) {
	if (n <= 0) {
		return false;
	}

	// 这里2可以替换为任意正整数m，就是计算m的幂次方
	while (n % 2 === 0) {
		n = parseInt(n / 2);
	}

	if (n === 1) {
		return true;
	} else {
		return false;
	}
}

/**
 * 采用位运算
 * @param n {number}
 * @return {boolean}
 * */

function isPowerOfTwo(n) {
	if (n <= 0) {
		return false;
	}
	// 如果存在非负整数 k 使得 n=2^k，则 n 的二进制表示为 1 后面跟 k 个0
	return n & (n - 1) === 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

拓展知识：采用循环除法的方法中，2可以替换为任意正整数m，就是计算m的幂次方。

2.求3的幂

力扣326题， 给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。整数 n 是 3 的幂次方需满足：存在整数 x 使得 $n==3^x$

分析：用除法思路与上题一样。这里说一下还可以用位运算的解决办法。我们知道 $3^0=1,3^1=3,3^2=9,...,3^{19}=1162261467$ ,在最大正整数范围之内，如果是3的幂就一定是1162261467的除数。

代码如下：

function isPowerOfThree(n) {
	if (n <= 0) {
		return false;
	}
	// 2^31 - 1内最大的3的幂为3^19=1162261467,只要n为1162261647的除数就说明是3的幂次方
	return (1162261467 % n) === 0;
}
1
2
3
4
5
6
7

3.求4的幂

力扣342 题，给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。整数 n 是 4 的幂次方需满足：存在整数 x 使得 $n==4^x$ 。

分析：第一种方法还是可以用循环除法。第二种方法就是位运算，这种方法可以在求2的幂的位运算解法进一步得出，$4^k$其实就是 $2^{2k}$ ，2的偶数次幂,判断二进制表示中1的位置是否出现在从低位开始的第偶数位上即可,这里规定最低位为第0位。比如n=16,其二进制表示为 $(00010000{)}_2$，1的位置为第4位。创建一个32位有符号整数$(10101010101010101010101010101010{)}_2$，让其偶数为0，奇数位为1，与n进行位与运算，如果结果为0，说明n为4的幂次方数，否则不是。为了使代码更简洁，还可以将创建的32位有符号整数用16进制表示，即 $(aaaaaaaa{)}_{16}$ , 也就是0xaaaaaaaa

代码如下：

function isPowerOfFour(n) {
	if (n <= 0) {
		return false;
	}

	return (n & (n - 1)) === 0 && (n & 0xaaaaaaaa) === 0;
}
1
2
3
4
5
6
7