Vue.js

Appearance

On this page

实战：4 的幂 ​

判断一个数是否是 4 的幂。

问题描述 ​

LeetCode 342. Power of Four

给定一个整数，写一个函数来判断它是否是 4 的幂次方。

示例：

输入：n = 16
输出：true (4^2 = 16)

输入：n = 8
输出：false (2^3 = 8，不是4的幂)

4 的幂的特点 ​

4 的幂是 2 的幂，但 1 只能出现在奇数位（从右数第 1, 3, 5... 位）：

1  = 0001  (位置 0)
4  = 0100  (位置 2)
16 = 10000 (位置 4)

解法一：位运算 ​

javascript
function isPowerOfFour(n) {
  // 是 2 的幂 且 1 在奇数位
  return n > 0 
    && (n & (n - 1)) === 0 
    && (n & 0x55555555) !== 0;
}

0x55555555 的二进制是 0101...0101，标记了所有奇数位。

解法二：取模 ​

4 的幂除以 3 余 1：

javascript
function isPowerOfFour(n) {
  return n > 0 
    && (n & (n - 1)) === 0 
    && n % 3 === 1;
}

为什么？4^k = (3+1)^k，展开后除了 1 其他项都能被 3 整除。

解法三：对数 ​

javascript
function isPowerOfFour(n) {
  if (n <= 0) return false;
  const log = Math.log(n) / Math.log(4);
  return Math.abs(log - Math.round(log)) < 1e-10;
}

注意浮点精度问题。

对比 2 的幂和 4 的幂 ​

条件2 的幂4 的幂
n > 0✓✓
n & (n-1) === 0✓✓
1 在奇数位-✓

复杂度 ​

  • 时间：O(1)
  • 空间：O(1)

三种方法详解 ​

方法一：位掩码 ​

javascript
function isPowerOfFour(n) {
  return n > 0 
    && (n & (n - 1)) === 0      // 是 2 的幂
    && (n & 0x55555555) !== 0;  // 1 在奇数位
}

0x55555555 的二进制是 01010101010101010101010101010101，标记了所有奇数位（0, 2, 4, 6...）。

方法二：取模 ​

javascript
function isPowerOfFour(n) {
  return n > 0 
    && (n & (n - 1)) === 0 
    && n % 3 === 1;
}

为什么 4^k % 3 = 1？

  • 4 = 3 + 1
  • 4^k = (3+1)^k = 3m + 1（二项式展开，除了 1^k 其他项都有 3 的因子）

方法三：对数 ​

javascript
function isPowerOfFour(n) {
  if (n <= 0) return false;
  const log4 = Math.log(n) / Math.log(4);
  return Number.isInteger(log4);
}

注意浮点精度问题，可能需要用 Math.round 配合误差判断。

执行过程 ​

以 n = 16 为例：

方法一：位掩码
  16 = 10000（二进制）
  16 > 0 ✓
  16 & 15 = 10000 & 01111 = 0 ✓（是 2 的幂）
  16 & 0x55555555 = 10000 & ...01010101 = 10000 ≠ 0 ✓
  结果：true

方法二：取模
  16 > 0 ✓
  16 & 15 = 0 ✓
  16 % 3 = 1 ✓
  结果：true

以 n = 8 为例：

方法一：位掩码
  8 = 1000（二进制）
  8 > 0 ✓
  8 & 7 = 1000 & 0111 = 0 ✓（是 2 的幂）
  8 & 0x55555555 = 1000 & ...01010101 = 0 ✗
  结果：false（1 在第 3 位，是偶数位）

方法二：取模
  8 > 0 ✓
  8 & 7 = 0 ✓
  8 % 3 = 2 ≠ 1 ✗
  结果：false

边界情况 ​

javascript
// n = 0
isPowerOfFour(0);  // false

// n = 1 = 4^0
isPowerOfFour(1);  // true

// n = 2（是 2 的幂，不是 4 的幂）
isPowerOfFour(2);  // false

// n = 4
isPowerOfFour(4);  // true

// 负数
isPowerOfFour(-4);  // false

4 的幂 vs 2 的幂 ​

2 的幂：1, 2, 4, 8, 16, 32, 64, 128...
4 的幂：1,    4,    16,     64...

4 的幂是 2 的幂的子集（指数为偶数）

二进制表示中 1 的位置：

1   = 0001  位置 0（偶数）✓ 4^0
2   = 0010  位置 1（奇数）✗
4   = 0100  位置 2（偶数）✓ 4^1
8   = 1000  位置 3（奇数）✗
16  = 10000 位置 4（偶数）✓ 4^2

常见错误 ​

错误一：忘记检查是否为 2 的幂 ​

javascript
// 错误：没有先判断是 2 的幂
function isPowerOfFour(n) {
  return n > 0 && n % 3 === 1;
}
// 7 % 3 = 1，但 7 不是 4 的幂

// 正确：
function isPowerOfFour(n) {
  return n > 0 && (n & (n-1)) === 0 && n % 3 === 1;
}

错误二：位掩码写错 ​

javascript
// 错误：用了偶数位掩码
n & 0xAAAAAAAA  // 10101010...标记偶数位

// 正确：奇数位掩码
n & 0x55555555  // 01010101...标记奇数位

相关题目 ​

题目难度关键点
342. 4的幂简单本题
231. 2的幂简单n & (n-1) = 0
326. 3的幂简单取模或对数
191. 位1的个数简单位运算基础

总结 ​

  1. 4 的幂特征：是 2 的幂，且 1 在偶数位（0, 2, 4...）
  2. 位掩码法：n & 0x55555555 检查位置
  3. 取模法：n % 3 === 1（数学证明）
  4. 组合判断：先判断 2 的幂，再判断特殊条件

在 GitHub 上编辑此页