「JavaScript」计算二进制中1的个数「位运算」💡

一、算法思路

问题描述： 给定一个 int 型正整数，计算其二进制表示中 1 的个数。

算法思路：

1. 位运算的核心思想：通过按位与运算 n & (n - 1)，可以消除最右边的一个 1。
   • 例如：n = 5（101），n & (n - 1) 等于 4（100）。
   • 这个操作的结果是将数字的二进制中最右边的 1 变为 0。
2. 不断消除 1，统计次数：
   • 每次执行 n & (n - 1) 后，计数器加 1。
   • 当 n 变为 0 时，循环结束。
3. 时间复杂度优越性：每次操作都会减少一个 1，所以最多执行的次数等于 1 的个数。

总结：利用 n & (n - 1) 的特性，可以高效地统计二进制中 1 的个数，而不需要逐位判断。

原理解释

1. 二进制中 n - 1 的特点

当我们对一个二进制数 n 减去 1 时，二进制的变化如下：

• 从右向左找到第一个 1，将它变为 0。
• 该 1 右边的所有 0 都会变为 1。

举例：

• 如果 n = 6（110）：
  • n - 1 = 5（101）。
• 如果 n = 8（1000）：
  • n - 1 = 7（0111）。

2. n & (n - 1) 的结果

按位与运算会比较两个二进制数的每一位：

• 如果对应位都是 1，结果为 1。
• 否则结果为 0。

当我们对 n 和 n - 1 执行 n & (n - 1) 时：

• n 的二进制中，最右边的 1 会被清零。
• 这是因为在 n - 1 中，最右边的 1 变为 0，而更右边的所有位变为 1，导致按位与结果清零。

二、Code

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    // 从标准输入读取整数
    let n = parseInt(await readline());

    // 统计二进制中 1 的个数
    let count = 0; // 初始化计数器

    // 核心逻辑：不断执行 n & (n - 1)
    while (n > 0) {
        n &= (n - 1); // 消除最右边的 1
        count++; // 每次消除一个 1，计数加 1
    }

    // 输出结果
    console.log(count);
}();

三、复杂度分析

1. 时间复杂度：
   • 每次操作都会移除一个 1，最多执行的次数等于二进制中 1 的个数。
   • 因此，时间复杂度是 O(k)，其中 k 是二进制中 1 的个数。
   • 对于 32 位整数，最坏情况下 k = 32，因此效率非常高。
2. 空间复杂度：
   • 仅使用了常数个变量（如 count 和 n），不需要额外空间。
   • 空间复杂度是 O(1)。