判断一个数是否为 2 的整数次幂

判断一个数是否为 2 的整数次幂

2 的整数次幂指的是
$$
2^0、 2^1、 2^2、 2^3 … 2^n
$$
从表面看,后者都比前者大 2;根据这个规律,那么可以从起始的 1 开始,与给定的数对比,如果不相等,则乘以 2 再与给定数对比,直到两个数相等或大于等于给定数为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* 判断给定数 n 是否为 2 的整数次幂
*
* @param n
*/
const isPowerOfTwo = (n) => {
if (n > 0 && Number.isInteger(n)) {
// n 为 奇数直接返回 false
if (n & 1 !== 0) return false;

let num = 1;

while (num <= n) {
if (n === num) return true;

// num = num * 2;
num = num << 1;
}

return false;
} else {
return false;
}
};

后面发现 2 的整数次幂还有另外一个共同点:
$$
2^0 = 1B
$$

$$
2^1 = 10B
$$

$$
2^2 = 100B
$$

$$
2^3 = 1000B
$$

$$
2^4=10000B
$$

$$
2^5=100000B
$$

将 2 的整数次幂转换成二进制之后,就会发现只有最高位是 1,其余位都是 0。之前通过 n & 1 的运算结果是否为 0 来判断奇偶性,这里也可以参考这种思路。将 2^n 与最高位为 0,其余位都是 1 的数(即 2^n - 1) 进行 & 运算,根据运算结果是否为 0 来判断是否为 2 的整数次幂。

1
2
3
4
5
6
7
8 & 7 = 2^3 & (2^3-1) = 1000 & 0111 = 0

9 & 8 = (2^3 + 1) & (2^3 + 1 - 1) = 1001 & 1000 = 1000

...

(2^n) & (2^n - 1) = 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* 判断给定数 n 是否为 2 的整数次幂
*
* @param n
*/
const isPowerOfTwo = (n) => {
if (n > 0 && Number.isInteger(n)) {
// n 为 奇数直接返回 false
if (n & 1 !== 0) return false;

return (n & (n - 1)) === 0;
} else {
return false;
}
};

对比上面两种算法,前者时间复杂度为 O(logn),后者的时间复杂度为 o(1)

总结:

  • 在恰当的时候利用位运算的特性来解决问题能提高不少效率
  • 尽量从多个维度分析问题