当前位置： 面试刷题>> 用O(1)时间检测整数n是否为2的幂 (经典算法题500道)
### 题目描述
设计一个算法，用于检测给定的整数`n`（`n > 0`）是否为2的幂。要求算法的时间复杂度为O(1)，即不依赖于输入`n`的大小。
### 解题思路
要检测一个数是否为2的幂，我们可以利用2的幂的一个特性：如果一个数是2的幂，那么它的二进制表示中只有一个`1`，其余位都是`0`。基于这个特性，我们可以通过位运算来检测。具体地，我们可以通过以下步骤判断：
1. 如果`n`小于等于0，则`n`不是2的幂。
2. 如果`n`和`n-1`进行按位与操作（`n & (n-1)`）的结果为`0`，则`n`是2的幂。这是因为如果`n`是2的幂，那么`n`的二进制形式为`100...0`（只有一个`1`），而`n-1`则为`011...1`（全为`1`，长度与`n`相同但少一位）。按位与操作会将两个数中对应的位都为`1`的位设为`1`，否则为`0`。因此，`n & (n-1)`的结果一定是`0`。
### 示例代码
#### PHP
```php
function isPowerOfTwo($n) {
if ($n <= 0) return false;
return ($n & ($n - 1)) === 0;
}
// 测试
echo isPowerOfTwo(16) ? "true" : "false"; // 输出 true
echo isPowerOfTwo(3) ? "true" : "false"; // 输出 false
```
#### Python
```python
def isPowerOfTwo(n):
if n <= 0:
return False
return (n & (n - 1)) == 0
# 测试
print(isPowerOfTwo(16)) # 输出 True
print(isPowerOfTwo(3)) # 输出 False
```
#### JavaScript
```javascript
function isPowerOfTwo(n) {
if (n <= 0) return false;
return (n & (n - 1)) === 0;
}
// 测试
console.log(isPowerOfTwo(16)); // 输出 true
console.log(isPowerOfTwo(3)); // 输出 false
```
### 码小课相关内容分享
码小课网站中包含了大量关于算法和数据结构的详细讲解和示例代码，非常适合想要深入学习算法和编程的同学们。在码小课，你可以找到关于位运算、动态规划、搜索算法等多种算法思想的深入剖析，以及通过实际案例来加深理解。无论你是初学者还是希望进阶的开发者，都能在码小课找到适合自己的学习资源。