一、题目
LeetCode-231. 2 的幂
链接：https://leetcode-cn.com/problems/power-of-two/
难度：简单
给你一个整数n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。
如果存在一个整数 x 使得 n == 2^x ，则认为 n 是 2 的幂次方。
示例 1：
输入：n = 1
输出：true
解释：2^0 = 1
示例 2：
输入：n = 16
输出：true
解释：2^4 = 16
示例 3：
输入：n = 3
输出：false
示例 4：
输入：n = 4
输出：true
提示：
-2^31 <= n <= 2^31 - 1
二、解题思路
如果n = 2^x且 x为自然数（即 n为 2 的幂），则一定满足以下条件：
- 恒有 n & (n - 1) == 0，因为n 二进制最高位为 1，其余所有位为 0；
n - 1二进制最高位为 0，其余所有位为 1； - 一定满足 n > 0。
因此，通过 n > 0 且 n & (n - 1) == 0 即可判定是否满足 n = 2^x。
| 2^x | n | n-1 | n&(n-1) |
|---|---|---|---|
| 2^0 | 0001 | 0000 | (0001) & (0000) == 0 |
| 2^1 | 0010 | 0001 | (0010) & (0001) == 0 |
| 2^2 | 0100 | 0011 | (0100) & (0011) == 0 |
| 2^3 | 1000 | 0111 | (1000) & (0111) == 0 |
三、实现过程
c++
class Solution {
public:
bool isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
};
PHP
class Solution {
/**
* @param Integer $n
* @return Boolean
*/
function isPowerOfTwo($n) {
return $n > 0 && ($n & ($n - 1)) == 0;
}
}
JavaScript
/**
* @param {number} n
* @return {boolean}
*/
var isPowerOfTwo = function(n) {
return n > 0 && (n & (n - 1)) == 0;
};
四、小结
- 时间复杂度：O(1)
- 空间复杂度：O(1)
