快速判断一个数是否是N的幂次方

这两天的每日一题全是跟这个有关系的, 故这里简单总结下, 应该说这是个技巧, 并不涉及很复杂的算法, 就是简单的位运算, 以及找出N的幂次方所具有的特征, 最后做到在$O(1)$的时间内判断出来.

题目链接:

Leetcode 231. 2的幂

Leetcode 342. 4的幂

Leetcode 326. 3的幂

2的幂

题目描述

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

如果存在一个整数 x 使得 n == $2^x$ ，则认为 n 是 2 的幂次方。

提示：

• $-2^{31}\le n\le 2^{31-1}$

给个限定条件 : 你能够不使用循环/递归解决此问题吗？

思路分析

如果没有限制条件的话, 那么解决这道问题的方法挺多的, 因为这里n的范围就是int类型的范围, 故我们还是可以枚举出在int范围内所有的2的幂次方. 这里可以用哈希表, 然后直接判断给定的n是否在哈希表里面即可. 当然也可以一直 mod 2, 然后再 / 2, 若中途发现mod 2 的结果不为0, 则证明不是2的幂次方, 不过这样要注意要特判1这个数字, 这两种方法都是有用到迭代循环来求解的,当然循环和递归是可以等价变形的. 那如何快速在$O(1)$的时间内判断出来呢, 这里我们就来看$2^x$的相关性质。

1. $2^x$的二进制表示是形如 : 1 0000, 0000,....,000 的这种形式, 即最高位是1其它位数全是0的这种形式
2. $2^x$的只包含因子2

low_bit算法

如果看第一个性质的话, 我们可以想到我们的low_bit算法

low_bit算法的实现

 n >> k & 1   //求n的第k位数字: n >> k & 1    //k是从第0位开始算起， 这里的移位运算符的优先级大于逻辑运算符

 n & -n       // 返回n的最后一位1的位置（二进制的第几位,  这里相当于补码与上原码 

我们常封装一个lowbit函数返回一个数二进制表示的是最低位的 1 及其后边所有的 0 构成的数值。, 例如 6 的二进制表示为 0000 ... 0110; 其最低位的1及后面的0构成的数为 10b， 那么lowbit(6) = 2;

auto lowbit(int n) -> int
{
	return n & -n;
}	

具体说明为啥让一个数和它的负数相与的结果就是该数二进制表示中最低位的 1 及其后边所有的 0 构成的数值。

故如果这个数是2的幂次方, 那么其low_bit算法得到的结果必然是和本身是相等的, 即low_bit(n) == n; 当然由于$2^x$ > 0；

故最后的代码实现为:

时间复杂度 $O(1)$

class Solution 
{
public:
    bool isPowerOfTwo(int n) 
    {
        return n > 0 && (n & -n) == n; 
    }
};

只包含因子2性质的作用

相比于上面的low_bit算法, 这种方法更加简单和更好理解, 这里的n范围为int类型的范围, 在这个范围内, 2的幂次方的最大值为 $2^{30}$, 故n如果是2的幂次方, 那么一定可以整除$2^{30}$, 即满足 (1 << 30) % n == 0;

class Solution 
{
public:
    bool isPowerOfTwo(int n) 
    {
        return n > 0 && (1 << 30) % n == 0; 
    }
};

4的幂

题目描述

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

如果存在一个整数 x 使得 n == $4^x$ ，则认为 n 是 4 的幂次方。

提示：

• $-2^{31}\le n\le 2^{31-1}$

给个限定条件 : 你能够不使用循环/递归解决此问题吗？

思路分析

同样分析 4的幂次方所具备的一些性质:

1. $4^x$ > 0

2. $4^x$ = $(2^2{)}^x$ = $(2^x{)}^2$, 故4的幂次方可以开根号, 且平方根为整数

3. 只包含因数2

依次分析每个性质需要满足的条件, 第一个性质只需满足 n > 0即可, 第二个性质n满足其平方根是一个整数, 故对n开根号得到的平方根r取整, 然后判断 r * r == n即可. 对于性质3那么就可以用上面的low_bit算法或者直接判断n是否能整除$2^{30}$ 。

代码实现

class Solution 
{
public:
    bool isPowerOfFour(int n) 
    {
        return n > 0 && (1 << 30) % n == 0 && (int)sqrt(n) * (int)sqrt(n) == n;
    }
};

3的幂

题目描述

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

如果存在一个整数 x 使得 n == $3^x$ ，则认为 n 是 3 的幂次方。

提示：

• $-2^{31}\le n\le 2^{31-1}$

给个限定条件 : 你能够不使用循环/递归解决此问题吗？

思路分析

同样分析 3的幂次方所具备的一些性质:

1. $3^x$ > 0

2. 只包含因数3

依次分析每个性质需要满足的条件, 第一个性质只需满足 n > 0即可, 第二个性质我们同样分析, 在int范围内3的幂次方最大为$3^x$ = $3^{19}$ = 1162261467. 即判断 n 能否整除 $3^{19}$. 即 $3^{19}$ % n == 0;

代码实现

class Solution 
{
public:
    bool isPowerOfThree(int n) 
    {
        return n > 0 && 1162261467 % n == 0;
    }
};

总结

故对于快速判断一个数是否是N的幂次方, 我们从题目条件入手的话, 可以在n的合理范围内找到N幂次方最大是多少, 如果一个数是N的幂次方, 必然能整除这个最大的N的幂次方. 其他限定条件的话, 可以参考4的幂次方的分析方法, 即我们将其性质分析出来,然后每个性质单独分析出判断代码即可.