点滴生活

Appearance

判断2的指数 ​

js
function isPowerOf2(x) {
    return (x & (x - 1)) === 0
}

这个函数 isPowerOf2 用于判断一个给定的数字 x 是否是 2 的幂次方。以下是它的工作原理：

解释： ​

  1. 2的幂次方的特性：

    • 2的幂次方的数在二进制表示中，只有一个 1，其余位都是 0。
    • 例如：
      • 1（2⁰）→ 0001
      • 2（2¹）→ 0010
      • 4（2²）→ 0100
      • 8（2³）→ 1000

  2. x - 1 的作用：

    • 如果 x 是 2 的幂次方，那么 x - 1 会把 x 的二进制中唯一的 1 变成 0，并且后面的所有位变成 1。
    • 例如：
      • 4（0100）→ 3（0011）
      • 8（1000）→ 7（0111）

  3. x & (x - 1) 的作用：

    • 如果 x 是 2 的幂次方，那么 x & (x - 1) 的结果一定是 0，因为 x 和 x - 1 的所有位都不同。
    • 例如：
      • 4 & 3 → 0100 & 0011 = 0000（0）
      • 8 & 7 → 1000 & 0111 = 0000（0）

  4. 特殊情况 x = 0：

    • 当 x = 0 时，0 & (0 - 1) = 0 & (-1) = 0，但 0 不是 2 的幂次方，因此需要额外判断 x > 0。

修正后的代码： ​

js
function isPowerOf2(x) {
    return x > 0 && (x & (x - 1)) === 0;
}

关键点： ​

  • 该函数可以正确判断 正整数 是否是 2 的幂次方。
  • 修正后的版本排除了 x = 0 的情况，避免误判。
  • 时间复杂度：O(1)（仅需一次位运算和比较）。

其他方法 ​

是的，除了使用 x & (x - 1) === 0 的方法，还有其他几种方式可以判断一个数是否是 2 的幂次方。以下是几种常见的方法：

方法 1：利用 Math.log2（对数法） ​

js
function isPowerOf2(x) {
    return x > 0 && Number.isInteger(Math.log2(x));
}

原理：

  • Math.log2(x) 计算 x 以 2 为底的对数。
  • 如果 x 是 2 的幂次方，则 Math.log2(x) 应该是整数。
  • Number.isInteger() 检查该对数是否为整数。

缺点：

  • 浮点数精度问题可能导致误判（如 Math.log2(8) 是 3，但 Math.log2(536870912) 可能因精度误差变成 29.000000000000004）。

方法 2：位运算（计算 1 的个数） ​

js
function isPowerOf2(x) {
    return x > 0 && (x.toString(2).match(/1/g) || []).length === 1;
}

原理：

  • 将 x 转为二进制字符串，检查其中 1 的个数是否恰好为 1。
  • 例如：
    • 4 → "100"（1 个 1）→ true
    • 5 → "101"（2 个 1）→ false

缺点：

  • 需要字符串转换，性能不如位运算高效。

方法 3：利用 x === (x & -x) ​

js
function isPowerOf2(x) {
    return x > 0 && x === (x & -x);
}

原理：

  • x & -x 会保留 x 的最低位的 1，其余位清零。
  • 如果 x 是 2 的幂次方，则 x 只有一个 1，所以 x & -x 仍然等于 x。
  • 例如：
    • 8 → 1000，-8（补码）→ ...1000 → 8 & -8 = 1000 & ...1000 = 1000（8）
    • 6 → 0110，-6 → ...1010 → 6 & -6 = 0110 & 1010 = 0010（2，不等于 6）

优点：

  • 比 x & (x - 1) 更直接，但需要理解补码机制。

方法 4：暴力枚举（适用于小范围） ​

js
function isPowerOf2(x) {
    if (x <= 0) return false;
    while (x % 2 === 0) x /= 2;
    return x === 1;
}

原理：

  • 不断除以 2，直到 x 变成奇数。
  • 如果最终 x === 1，说明它是 2 的幂次方。

缺点：

  • 效率较低，不推荐用于大数计算。

方法 5：查表法（适用于已知范围） ​

js
const powerOf2Set = new Set([1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024 /* ... */]);
function isPowerOf2(x) {
    return powerOf2Set.has(x);
}

适用场景：

  • 如果已知 x 的范围较小（如 32 位整数），可以预计算所有可能的 2 的幂次方，存入 Set 进行快速查找。

缺点：

  • 占用额外内存，不适用于任意大数。

总结 ​

方法时间复杂度适用场景缺点
x & (x - 1) === 0O(1)通用需排除 x = 0
Math.log2O(1)数学计算浮点精度问题
统计 1 的个数O(log x)直观字符串操作较慢
x === (x & -x)O(1)位运算优化需理解补码
暴力枚举O(log x)教学示例效率低
查表法O(1)固定范围占用内存

推荐方法：

  • 最优解：x > 0 && (x & (x - 1)) === 0（高效、简洁）。
  • 替代方案：x > 0 && x === (x & -x)（同样高效，但可读性稍差）。