LeetCode 0231. 2 的幂
【LetMeFly】231.2 的幂
力扣题目链接：https://leetcode.cn/problems/power-of-two/
给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。
如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。
示例 1：
输入：n = 1 输出：true 解释：20 = 1
示例 2：
输入：n = 16 输出：true 解释：24 = 16
示例 3：
输入：n = 3 输出：false
示例 4：
输入：n = 4 输出：true
示例 5：
输入：n = 5 输出：false
提示：
-231 <= n <= 231 - 1
进阶：你能够不使用循环/递归解决此问题吗？
方法一：位运算 + 负数特判
如果一个数是2的幂，那么这个数的二进制表示中只有一个1，其余全是0。
因此，我们只需要统计 n n n在二进制下的 1 1 1的个数即可。
注意： 当 n n n是负数的时候，C++中算术右移，什么时候都不会变成0（最终会变成-1（每一位都是1））。
如果想要逻辑右移，那么需要把int转为unsigned int。
- 时间复杂度 O ( log n ) O(\log n) O(logn)
- 空间复杂度 O ( 1 ) O(1) O(1)
AC代码
C++
class Solution {
public:
bool isPowerOfTwo(int n) {
if (n < 0)
return false;
int cnt1 = 0;
while (n) {
if (n & 1)
cnt1++;
n >>= 1;
}
return cnt1 == 1;
}
};
方法二：转为unsigned int + INT_MIN特判
32位整数的最小数为
−
2
31
−
1
-2^{31}-1
−231−1，其二进制（补码表示）为1000 0000 0000 0000 0000 0000 0000 0000
原因是：
2
31
2^{31}
231为1000 0000 0000 0000 0000 0000 0000 0000
补码 = 原码最高位为1，其余位取反再加一
最高位不变，其余位取反：1111 1111 1111 1111 1111 1111 1111 1111
其余位加一：111 1111 1111 1111 1111 1111 1111 1111 + 1= 1000 0000 0000 0000 0000 0000 0000 0000
首位的1溢出了，最终补码为1000 0000 0000 0000 0000 0000 0000 0000
也就是说，有且仅有这一个32位负整数，二进制下只有1个1。
因此，转为unsigned int的话，需要特判一下是否为IINT_MIN
AC代码
C++
class Solution {
public:
bool isPowerOfTwo(unsigned int n) {
if (n == INT_MIN)
return false;
int cnt1 = 0;
while (n) {
if (n & 1)
cnt1++;
n >>= 1;
}
return cnt1 == 1;
}
};
如果觉得修改参数类型不好，也可：
class Solution {
public:
bool isPowerOfTwo(int n) {
unsigned int un = n;
if (un == INT_MIN)
return false;
int cnt1 = 0;
while (un) {
if (un & 1)
cnt1++;
un >>= 1;
}
return cnt1 == 1;
}
};
同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/126766929