Vue.js

Appearance

On this page

实战：位 1 的个数 ​

统计一个整数的二进制表示中有多少个 1。

问题描述 ​

LeetCode 191. Number of 1 Bits

编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字 1 的个数。

示例：

输入：n = 11 (二进制 1011)
输出：3

解法一：逐位检查 ​

javascript
function hammingWeight(n) {
  let count = 0;
  while (n !== 0) {
    count += n & 1;
    n = n >>> 1;  // 无符号右移
  }
  return count;
}

时间：O(32)

解法二：Brian Kernighan 算法 ​

每次清除最右边的 1：

javascript
function hammingWeight(n) {
  let count = 0;
  while (n !== 0) {
    n = n & (n - 1);
    count++;
  }
  return count;
}

时间：O(k)，k 是 1 的个数。

n & (n-1) 的原理 ​

n     = 1011000
n-1   = 1010111
n&(n-1) = 1010000

最右边的 1 被清除了！

执行过程 ​

n = 11 = 1011

第1轮：n = 1011 & 1010 = 1010, count = 1
第2轮：n = 1010 & 1001 = 1000, count = 2
第3轮：n = 1000 & 0111 = 0000, count = 3

结果：3

应用 ​

这个技巧在很多问题中有用：

  • 判断 2 的幂
  • 计算汉明距离
  • 统计状态压缩中的元素个数

复杂度 ​

  • 时间：O(k)，k 是 1 的个数
  • 空间：O(1)

两种方法对比 ​

方法时间循环次数原理
逐位检查O(32)固定 32 次检查每一位
Brian KernighanO(k)k 次（1的个数）每次消除一个 1

当 1 的个数较少时，Brian Kernighan 更快。

详细执行过程 ​

以 n = 11（二进制 1011）为例：

逐位检查法：

n = 1011

检查位0：1011 & 1 = 1, count = 1, n = 0101
检查位1：0101 & 1 = 1, count = 2, n = 0010
检查位2：0010 & 1 = 0, count = 2, n = 0001
检查位3：0001 & 1 = 1, count = 3, n = 0000
...（继续检查到第31位）

结果：3

Brian Kernighan 法：

n = 1011

第1轮：n-1 = 1010
        n & (n-1) = 1011 & 1010 = 1010, count = 1

第2轮：n-1 = 1001
        n & (n-1) = 1010 & 1001 = 1000, count = 2

第3轮：n-1 = 0111
        n & (n-1) = 1000 & 0111 = 0000, count = 3

n = 0，结束

结果：3（只循环了 3 次）

边界情况 ​

javascript
// n = 0
hammingWeight(0);  // 0

// n = 1
hammingWeight(1);  // 1

// 全 1（32位无符号最大值）
hammingWeight(0xFFFFFFFF);  // 32

// 2 的幂（只有一个 1）
hammingWeight(1024);  // 1

常见错误 ​

错误一：使用有符号右移 ​

javascript
// 错误：>> 会保留符号位，负数会死循环
while (n !== 0) {
  count += n & 1;
  n = n >> 1;  // 负数右移永远不会变成 0
}

// 正确：>>> 无符号右移
n = n >>> 1;

错误二：n & (n-1) 理解错误 ​

javascript
// n & (n-1) 消除的是最低位的 1，不是最高位
// 所以循环次数等于 1 的个数

查表法（最快） ​

预计算 0-255 每个数的 1 个数：

javascript
const table = new Array(256);
for (let i = 0; i < 256; i++) {
  table[i] = (i & 1) + table[i >> 1];
}
table[0] = 0;

function hammingWeight(n) {
  return table[n & 0xff] + 
         table[(n >> 8) & 0xff] + 
         table[(n >> 16) & 0xff] + 
         table[(n >> 24) & 0xff];
}

时间 O(1)，空间 O(256)。

相关题目 ​

题目难度关键点
191. 位1的个数简单本题
231. 2的幂简单n & (n-1) = 0
338. 比特位计数简单批量计算
461. 汉明距离简单XOR + 本题

总结 ​

  1. 核心技巧：n & (n-1) 消除最低位的 1
  2. 时间优化：Brian Kernighan 法只循环 k 次
  3. 空间换时间：查表法 O(1) 时间
  4. 应用场景：状态压缩中统计选中元素个数

在 GitHub 上编辑此页