2的幂
📌 定义
给定一个整数 n，判断它是否是 2 的幂次方。即判断是否存在整数 x，使得 n = 2^x。
示例:
输入: n = 1
输出: true
解释: 2^0 = 1
输入: n = 16
输出: true
解释: 2^4 = 16
输入: n = 3
输出: false
输入: n = 5
输出: false
核心思路
2的幂的二进制特征：
- 2的幂在二进制中只有一个 1
- 例如：1(1), 2(10), 4(100), 8(1000), 16(10000)
关键技巧：
使用 n & (n - 1) 去掉最右边的 1，如果结果为 0，说明只有一个 1
示例:
n = 8 (1000)
n - 1 = 7 (0111)
n & (n - 1) = 1000 & 0111 = 0000 ✓
n = 6 (110)
n - 1 = 5 (101)
n & (n - 1) = 110 & 101 = 100 ≠ 0 ✗
复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 循环除法 | O(log n) | O(1) | 不断除以2 |
| 位运算 | O(1) | O(1) | n & (n-1) |
| 二进制统计 | O(log n) | O(1) | 统计1的个数 |
| 数学方法 | O(log n) | O(1) | 对数判断 |
Go 代码
Go 实现
package main
import (
"fmt"
"math"
)
// 方法1: n & (n - 1)
func isPowerOfTwo(n int) bool {
return n > 0 && (n&(n-1)) == 0
}
// 方法2: n & -n
func isPowerOfTwoV2(n int) bool {
return n > 0 && (n&-n) == n
}
// 方法3: 统计1的个数
func isPowerOfTwoCount(n int) bool {
if n <= 0 {
return false
}
count := 0
for n > 0 {
count += n & 1
n >>= 1
if count > 1 {
return false
}
}
return count == 1
}
// 方法4: 数学方法
func isPowerOfTwoMath(n int) bool {
if n <= 0 {
return false
}
logVal := math.Log2(float64(n))
return logVal == float64(int(logVal))
}
// 方法5: 循环除法
func isPowerOfTwoLoop(n int) bool {
if n <= 0 {
return false
}
for n%2 == 0 {
n /= 2
}
return n == 1
}
func main() {
testCases := []int{1, 2, 3, 4, 5, 8, 16, 1024}
for _, n := range testCases {
result := isPowerOfTwo(n)
fmt.Printf("%d 是2的幂: %v\n", n, result)
}
}思路展开
方法1详解：n & (n - 1)
2的幂的特点:
- 二进制中只有一个1
- n & (n - 1) 会去掉最右边的1
示例1: n = 8 (2^3)
n = 1000
n - 1 = 0111
n & (n - 1) = 1000 & 0111 = 0000 ✓
示例2: n = 6 (非2的幂)
n = 0110
n - 1 = 0101
n & (n - 1) = 0110 & 0101 = 0100 ≠ 0 ✗
示例3: n = 16 (2^4)
n = 10000
n - 1 = 01111
n & (n - 1) = 10000 & 01111 = 00000 ✓
方法2详解：n & -n
n & -n 的作用：获取最右边的1
示例1: n = 8 (2^3)
n = 00001000
-n = 11111000 (补码)
n & -n = 00001000 = 8 = n ✓
示例2: n = 6 (非2的幂)
n = 00000110
-n = 11111010
n & -n = 00000010 = 2 ≠ n ✗
原理:
- 如果n是2的幂，只有一个1
- n & -n 会保留这唯一的1
- 结果应该等于n本身
边界情况处理
特殊情况:
1. n <= 0: 返回 false
- 0 不是2的幂
- 负数不是2的幂
2. n = 1: 返回 true
- 1 = 2^0
3. n = 2^31: 可能溢出
- 使用long long避免溢出
- 或者限制n的范围
经典题目
LeetCode 问题
扩展问题
- 3的幂（不能用位运算）
- 判断是否为2的幂次方的和
⚖️ 优缺点
优点
- ✅ 时间复杂度 O(1)：只需一次位运算
- ✅ 空间复杂度 O(1)：不需要额外空间
- ✅ 代码简洁：一行代码解决
- ✅ 效率高：位运算速度快
缺点
- ❌ 不够直观：需要理解位运算原理
- ❌ 仅适用于2的幂：不能推广到其他底数
🎨 应用场景
- 容量与边界检查：判断缓冲区、哈希表或分块大小是否为 2 的幂，便于使用位掩码取模。
- 树与堆的层级计算：完全二叉树的层级边界常由 2 的幂决定。
- 算法前置条件：FFT、循环缓冲区等实现经常要求容量为 2 的幂。
💡 优化技巧
- 最常用写法是
n > 0 && n&(n-1) == 0，先判断正数避免0被误判。 - 如果只需要判断一个整数，不要循环除以 2；位运算可以在固定机器字长内完成。
n & -n == n也能判断 2 的幂，但依赖补码语义，可读性通常不如n&(n-1)。