4的幂
📌 定义
给定一个整数 n，判断它是否是 4 的幂次方。即判断是否存在整数 x，使得 n = 4^x。
要求：不能使用循环或递归
示例:
输入: n = 1
输出: true
解释: 4^0 = 1
输入: n = 16
输出: true
解释: 4^4 = 16
输入: n = 5
输出: false
输入: n = 8
输出: false (8是2的幂，但不是4的幂)
核心思路
4的幂的特征：
- 首先必须是 2的幂
- 二进制中的 1 必须在偶数位上（从右往左，位置从0开始）
4的幂的二进制表示:
4^0 = 1 = 0000...0001 (第0位)
4^1 = 4 = 0000...0100 (第2位)
4^2 = 16 = 0001...0000 (第4位)
4^3 = 64 = 0100...0000 (第6位)
4^4 = 256 = 1...00000000 (第8位)
规律: 1在第 0, 2, 4, 6, 8... 位（偶数位）
解决方案：
- 方法1：
n & (n-1) == 0且n & 0xAAAAAAAA == 0 - 方法2：
n & (n-1) == 0且(n-1) % 3 == 0
复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 位掩码 | O(1) | O(1) | 使用0xAAAAAAAA |
| 模3运算 | O(1) | O(1) | (n-1) % 3 |
| 循环除法 | O(log n) | O(1) | 不断除以4（不符合要求） |
| 对数法 | O(1) | O(1) | log4(n) 是否为整数 |
Go 代码
Go 实现
package main
import (
"fmt"
"math/bits"
)
// 方法1: 位掩码
func isPowerOfFour(n int) bool {
return n > 0 &&
(n&(n-1)) == 0 &&
(n&0xAAAAAAAA) == 0
}
// 方法2: 模3运算
func isPowerOfFourMod3(n int) bool {
return n > 0 &&
(n&(n-1)) == 0 &&
(n-1)%3 == 0
}
// 方法3: 位置检查
func isPowerOfFourPosition(n int) bool {
if n <= 0 {
return false
}
if (n & (n - 1)) != 0 {
return false
}
// 统计1的位置
position := 0
temp := n
for temp > 1 {
temp >>= 1
position++
}
return position%2 == 0
}
// 方法4: 使用内置函数
func isPowerOfFourBuiltin(n int) bool {
if n <= 0 {
return false
}
if (n & (n - 1)) != 0 {
return false
}
// bits.TrailingZeros 统计尾随0的个数
return bits.TrailingZeros(uint(n))%2 == 0
}
func main() {
testCases := []int{1, 2, 4, 5, 8, 16, 64, 256}
for _, n := range testCases {
result := isPowerOfFour(n)
fmt.Printf("%d 是4的幂: %v\n", n, result)
}
}思路展开
方法1详解：位掩码 0xAAAAAAAA
0xAAAAAAAA 的二进制:
10101010101010101010101010101010
特点: 奇数位（1, 3, 5, 7...）全是1
4的幂的1在偶数位:
4^0 = 1 = ...00000001 (第0位) ✓
4^1 = 4 = ...00000100 (第2位) ✓
4^2 = 16 = ...00010000 (第4位) ✓
2的幂但非4的幂的1在奇数位:
2^1 = 2 = ...00000010 (第1位) ✗
2^3 = 8 = ...00001000 (第3位) ✗
验证:
n = 16 (第4位)
16 & 0xAAAAAAAA = 0 ✓
n = 8 (第3位)
8 & 0xAAAAAAAA = 8 ≠ 0 ✗
方法2详解：模3运算
观察4的幂减1:
4^0 - 1 = 0 → 0 % 3 = 0
4^1 - 1 = 3 → 3 % 3 = 0
4^2 - 1 = 15 → 15 % 3 = 0
4^3 - 1 = 63 → 63 % 3 = 0
数学证明:
4^x - 1 = (2^2)^x - 1
= 2^(2x) - 1
= (2^2 - 1) × (2^(2x-2) + 2^(2x-4) + ... + 2^2 + 1)
= 3 × (...)
∴ 能被3整除 ✓
2的幂但非4的幂:
2^1 - 1 = 1 → 1 % 3 = 1 ✗
2^3 - 1 = 7 → 7 % 3 = 1 ✗
2^5 - 1 = 31 → 31 % 3 = 1 ✗
规律: 2^(2k) - 1 ≡ 0 (mod 3)
2^(2k+1) - 1 ≡ 1 (mod 3)
4的幂 vs 2的幂
2的幂:
1 = 0001 (2^0) → 4的幂 ✓
2 = 0010 (2^1) → 非4的幂
4 = 0100 (2^2) → 4的幂 ✓
8 = 1000 (2^3) → 非4的幂
16 = 00010000 (2^4) → 4的幂 ✓
32 = 00100000 (2^5) → 非4的幂
64 = 01000000 (2^6) → 4的幂 ✓
规律:
- 所有4的幂都是2的幂
- 4的幂 = 2^(偶数)
- 1的位置在偶数位（从0开始）
经典题目
LeetCode 问题
扩展问题
- 判断是否为2^n × 3
- 判断是否为完全平方数
⚖️ 优缺点
优点
- ✅ 时间复杂度 O(1)：常数时间判断
- ✅ 空间复杂度 O(1)：不需要额外空间
- ✅ 无需循环：满足题目要求
- ✅ 多种方法：可根据场景选择
缺点
- ❌ 不够直观：需要理解位运算
- ❌ 仅适用于4的幂：不能推广到其他底数
🎨 应用场景
💡 优化技巧
💡 为什么 4^x - 1 能被3整除？
数学推导:
4^x - 1 = (2^2)^x - 1
= 2^(2x) - 1
利用恒等式: a^n - 1 = (a-1)(a^(n-1) + a^(n-2) + ... + a + 1)
2^(2x) - 1 = (2-1)(2^(2x-1) + 2^(2x-2) + ... + 2 + 1)
= 2^(2x-1) + 2^(2x-2) + ... + 2 + 1
或者用模运算:
4 ≡ 1 (mod 3)
4^x ≡ 1^x ≡ 1 (mod 3)
4^x - 1 ≡ 0 (mod 3) ✓
对比:
2 ≡ -1 (mod 3)
2^(2x) ≡ (-1)^(2x) ≡ 1 (mod 3) → 4的幂
2^(2x+1) ≡ (-1)^(2x+1) ≡ -1 (mod 3) → 非4的幂