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

如何判断一个数是否为2的整数次幂 题目

实现一个方法，来判断一个正整数是否是2的整数次幂（如16是2的4次方，返回1；18不是2的整数次幂，则返回-1）。

---

法一

int isPowerOf2V1(int num) {
	int temp = 1;
	while (temp <= num) {
		if (temp == num) {
			return 1;
		}
		temp *= 2;
	}
	return -1;
}

创建一个中间变量temp，初始值是1。然后进入一个循环，每次循环都让temp和目标整数相比较，如果相等，则说明目标整数是2的整数次幂；如果不相等，则让temp增大一倍，继续循环并进行比较。当temp的值大于目标整数时，说明目标整数不是2的整数次幂。
例如，给出一个整数19，则
1×2=2，2×2=4，4×2=8，8×2=16，16×2=32，由于32>19，所以19不是2的整数次幂。
如果目标整数的大小是n，则此方法的时间复杂度是O(logn)。

优化一下

可以把之前乘以2的 *** 作改成向左移位，移位的性能比乘法高得多。

int isPowerOf2V2(int num) {
	int temp = 1;
	while (temp <= num) {
		if (temp == num) {
			return 1;
		}
		temp <<= 1;
	}
}

这样确实有一定优化，但算法的时间复杂度仍是O(logn)，本质上没有变。

---

法二

先把2的正整数次幂转换成二进制数，如下表

十进制二进制是否为2的整数次幂81000B是1610000B是32100000B是641000000B是1001100100B否

接下来如果把这些2的整数次幂各自减1

十进制二进制原数值-1是否为2的整数次幂81000B111B是1610000B1111B是32100000B11111B是641000000B111111B是1001100100B1100011B否

这时如果将原数值和它减1的结果进行按位与计算，也就是n&(n-1)

十进制二进制原数值-1n&n-1是否为2的整数次幂81000B111B0是1610000B1111B0是32100000B11111B0是641000000B111111B0是1001100100B1100011B1否

所以对于一个整数n，只需要计算n&(n-1)的结果是不是0就可以判断了。
时间复杂度为O(1)。

int isPowerOf2V3(int num) {
	return (num & num-1) == 0;
}