企业官网建设流程全解析

今天写的是 2026/01/19 的算法练习，题目很朴素：位1的个数。刚看题的人常以为这就是“把二进制数一遍”，但实际写起来，符号位、右移方式、循环次数这些细节，能把人坑到怀疑人生。这篇文章我会从最直观的逐位检查法开始，一路讲到 Brian Kernighan 算法、8 位查表法，以及 CPU 内置的 popcount 指令，最后再聊几个它最常见的变体和面试追问。适合刚接触位运算的初学者，也适合准备面试、想把这题真正讲清楚的人。

1. 先想清楚：位1个数到底在考什么

1.1 用一个10分钟的小例子建立直觉

题目本身不难理解：给定一个整数，统计它的二进制表示里有多少个“1”，英文一般叫 Hamming Weight 或 popcount。比如数字 11，二进制是 1011，那答案就是 3；数字 8，二进制是 1000，答案就是 1；数字 0 答案是 0。

很多人第一反应是：把数字转成字符串或者数组，然后一个个数“1”。这在刷题阶段不算错，但它绕开了这道题真正想考的东西——你能不能直接操作二进制位。整数在计算机里本来就是二进制存储的，你偏要把它转成十进制字符串再去数，相当于先绕着操场跑一圈再进门，时间和内存都白花了。

我习惯用一个类比来理解这道题：把整数的每一位想象成一盏灯，1 是亮，0 是灭。题目就是要你数一数总共有几盏灯亮着。位运算的&、|、^、~、<<、>>，本质上就是对这些“灯”做开关控制。你一旦形成这种画面，后面所有解法都顺了。

这道题在面试里出现的频率很高，因为它短小但信息密度大：既能考察你对二进制、补码、右移这些基础知识的掌握程度，又能通过“你用了几个解法”看出你的知识广度。常见的问法是在 LeetCode 这类平台上出现的 191 题，要求统计一个无符号整数的二进制中 1 的个数。平台一般会用 32 位整数来测，但工程里 64 位、128 位数字也会碰到，原理完全一样。

1.2 位运算在实际工程里的三个典型场景

别以为位运算只活在算法题里。实际项目里，统计“二进制里有多少个1”这件事经常悄悄出现。

第一个典型场景是权限系统。很多系统用整数的每一位代表一种权限，比如第 0 位是读、第 1 位是写、第 2 位是执行。用户权限合并之后就是一个整数，有时候你需要知道某个角色究竟开了几项权限，这时候“数1”就是刚需。

第二个场景是网络协议里的标志位。TCP 头、IP 头里全是按位排列的 flag，抓包分析时经常要统计某个字段里有多少个位置被置位。我之前排查一类协议日志时，需要从几万个 32 位整数里统计置位分布，当时直接写了乘法循环，结果跑了半天。后来换成数学技巧和查表法，速度明显改善，这也是我对这道题印象很深的原因。

第三个场景是布隆过滤器、位图索引这类大数据结构。布隆过滤器底层是一个位数组，判断元素是否存在需要看多个哈希位置是否都为 1，有时也要统计整个位数组的置位率。位数组通常被封装成若干个 64 位整数，统计总置位数时，就是在做“位1的个数”。

理解了这些场景，你就能明白为什么这道题值得好好学：它不是孤立的知识点，而是很多底层系统的公共零件。

1.3 暴力解其实没那么不堪，先写对再说

在玩花活之前，我还是建议先写一版最朴素的解法，把它当成正确性锚点。这里说的暴力解不是转字符串，而是用数学方法：模拟“不断取出最低位”。要取出十进制数的最低位，你可以对 10 取模；要取出二进制数的最低位，你就对 2 取模。

比如 n = 11，最低位是 1，记录下来，然后 n 变成 5；5 对 2 取模是 1，记录，n 变成 2；2 对 2 取模是 0，记录，n 变成 1；1 对 2 取模是 1，记录，n 变成 0。整个过程得到 1、1、0、1，共 3 个 1，结果正确。

这个方法的本质是“除 2 取余”，和十进制转二进制的手算过程一样。它的问题在于，取模和除法在 CPU 上比位运算慢不少，而且循环次数取决于二进制位数，最坏情况下要跑几十次。不过作为第一版答案，它的逻辑最直白，也最容易验证正确。你后面用任何高级解法，都可以拿它来对拍结果。

2. 最稳的写法：逐位检查法的完整实现与边界处理

2.1 思路一句话：不断看最低位，然后右移

暴力解用除法取余来看最低位，其实有更贴近底层的做法：用 n & 1 取出最低位，再用右移把这一位移出去。

为什么 n & 1 能取出最低位？因为 1 的二进制是 000...001，和 n 做按位与之后，只有最低位被保留下来。如果 n 最低位是 1，结果就是 1；如果最低位是 0，结果就是 0。这比取模运算快得多，而且语义非常清楚。

代码框架是这样的：先初始化 count = 0，然后进入循环。每次先用 count += (n & 1) 记录当前最低位是不是 1，再把 n 右移一位。循环什么时候结束？如果你知道输入固定是 32 位整数，那就固定循环 32 次；如果你只判断 n != 0，那也可以提前结束。两种写法我都见过，固定循环更稳，不容易漏掉高位补进来的内容。

这里有一个新手经常踩的坑：右移分逻辑右移和算术右移。逻辑右移就是在左边补 0；算术右移是在左边补符号位，也就是原数的最高位，正数补 0，负数补 1。如果你用了错误的右移方式，遇到负数时循环可能永远结束不了，或者结果完全错误。下一节我具体说。

2.2 Java/C 实现：为什么要用无符号右移 >>> 而不是 >>

先看 Java 代码：

public int hammingWeight(int n) { int count = 0; while (n != 0) { count += (n & 1); n >>>= 1; // 无符号右移，左边补0 } return count; }

这里我用了 >>> 而不是 >>。区别在于：>>> 是逻辑右移，高位一律补 0；>> 是算术右移，高位补符号位。

你可以试一个极端例子：n = -1。在 32 位补码表示里，-1 是全 1，也就是 0xFFFFFFFF。如果我用 >>，每移一位，左边补进来的还是 1，于是 n 从 0xFFFFFFFF 右移后仍然是 0xFFFFFFFF，永远不会变成 0，循环就死循环了。而用 >>>，左边补 0，移一次变成 0x7FFFFFFF，移 32 次之后变成 0，循环正常结束。

C/C++ 的情况稍有不同，标准里没有 Java 那种显式的 >>>。通常我建议直接用无符号类型：

int hammingWeight(uint32_t n) { int count = 0; while (n) { count += n & 1; n >>= 1; } return count; }

uint32_t 的右移就是逻辑右移，所以这里 >> 没有歧义。如果你非要用 int，就得小心负数右移补 1 的问题，处理起来很容易出 bug。我的原则是：写位运算优先用无符号类型，让语义自己说话。

2.3 Python 实现：注意负数会右移成死循环

Python 的整数没有固定位数，写这道题时也有自己的坑。很多人直接照搬：

def hammingWeight(n): count = 0 while n: count += n & 1 n >>= 1 return count

这段代码处理正数没问题，但一旦 n 是负数，就出大事了。Python 里负数的二进制概念是“无限多位的补码”，-1 右移永远还是 -1，循环会一直跑下去。所以如果你不确定输入语义，别用 while n 这样的判断。

更稳妥的写法是固定循环次数。既然题目说的是 32 位无符号整数，那就循环 32 次：

def hammingWeight(n): count = 0 for _ in range(32): count += n & 1 n >>= 1 return count

固定循环次数之后，就算是负数也能在 32 次内结束，因为每次都是逻辑移位般的右移，不再依赖判断 n 是否为 0。Python 3.10 之后其实直接有 int.bit_count() 方法，一行就能拿结果，这是内置优化，后面章节我会单独展开。这里先用逐位循环帮助你理解原理。

2.4 复杂度与适用场景

逐位检查法的复杂度很好算：时间上需要循环 O(k) 次，k 就是整数的位数，32 位整数就是 O(1) 但循环 32 次，严格说常数比较大；空间上是 O(1)，只用了计数器变量。

这个写法最大的价值是“好懂、不易错、方便调试”。你在面试里如果一时想不出更漂亮的解法，先把这个版本写出来，起码能拿基础分。工程里如果只是偶尔数一次 1，这种写法也完全够用，代码清晰，维护成本低。但如果数据量很大，比如每秒要统计上百万个整数的置位数，这种逐位循环就会成为性能瓶颈，这时候就需要换更高效的方案。

3. Brian Kernighan 算法：循环次数和1的个数一样

3.1 核心原理：n & (n - 1) 为什么能清除最低位的1

逐位检查法的循环次数取决于位数，不管你的数里有几个 1，32 位整数最多就要跑 32 次。Brian Kernighan 算法厉害的地方是：它循环的次数只等于 1 的个数。也就是说，如果一个数只有 3 个 1，它就跑 3 次。

核心就一行式子：n = n & (n - 1)。这个式子能把 n 最低位的那个 1 变成 0，而不影响其他位。

为什么？我们举个例子。假设 n = 12，二进制是 1100。n - 1 = 11，二进制是 1011。你看，从最低位开始，12 是 1100，最低位是 0，借位会一直向前，直到碰到第一个 1，也就是从低位往高位数第 3 位那个 1。n - 1 之后，这个 1 变成 0，而它右边的 0 全部变成 1，所以 1100 变成 1011。把 1100 和 1011 做按位与，结果是 1000，也就是 8。最低位的那个 1 确实被清掉了，其他的 1 保留了下来。

这里有个直观的理解方式：n - 1 像是一次“借位操作”，它一定会把 n 最低位的那个 1 给“拆掉”，并把后面低位的 0 都反转为 1。再和原数相与，这些被反转出来的 1 又会被原数中的 0 清零，最终效果就是把最低位的 1 抹掉。这个过程就像你从一堆亮灯里一盏一盏关掉最低位的亮灯，每关一次就计数一次，直到全灭。

3.2 极简代码与逐步走查

Kernighan 算法的代码极其简短：

public int hammingWeight(int n) { int count = 0; while (n != 0) { n &= (n - 1); count++; } return count; }

拿 n = 11 走一遍：11 的二进制是 1011。第一次 n & (n - 1)，n - 1 = 10，二进制 1010，相与得到 1010，等于 10，count 变成 1。第二次 n = 10，n - 1 = 9，二进制 1001，相与得到 1000，等于 8，count 变成 2。第三次 n = 8，n - 1 = 7，二进制 0111，相与得到 0，count 变成 3。循环结束，答案是 3。

注意这个式子对 0 也安全：如果 n = 0，n - 1 = -1，n & (n - 1) 等于 0，不过我们本来就不进循环，所以没问题。当然如果你用的是有符号整型，要确保 while 条件是 n != 0，而不是 n > 0，否则处理负数时会出问题。原因和前面类似，负数补码里的位很多，直接 n != 0 是安全的。

3.3 面试常追问的两个点

面试官看到你写出这个式子，通常会追问两个问题：第一，为什么它能清掉最低位的 1？第二，它的时间复杂度是多少？

第一个问题的答案就是我上面讲的借位分析：n - 1 会把最低位的 1 变成 0，同时把更低位的 0 变成 1，相与后这些位全部清零。你最好能在白板上画一下 1100 和 1011 的相与过程，用图示说话，比背结论可信得多。

第二个问题的标准答案是 O(k)，其中 k 是二进制中 1 的个数。最好情况是 n 是 2 的幂，只有 1 个 1，所以只循环 1 次；最坏情况是 n 是 -1（全 1），需要循环 32 次。从平均意义上看，它通常比逐位检查法快，因为很多随机数的 1 个数远小于 32。

这个式子还有一个衍生考点：判断一个数是不是 2 的幂。2 的幂的二进制只有一个 1，所以 n & (n - 1) == 0 就是判断条件。很多人能背这个结论，但如果你理解了借位原理，就不需要背，自己就能推出来。这道题的变体也常常连环出现：判断一个数是否是 2 的幂、去掉最低位的 1 后还剩多少、统计两个数有多少位不同……根子都是同一个式子。

3.4 我为什么建议刷题时优先写这个版本

如果你是在面试或者刷题，我个人建议优先写 Kernighan 版本。理由有三点。

第一，代码量最少，几乎不可能写错边界条件。逐位法还要考虑用 >>> 还是 >>，用 while n 还是固定循环；Kernighan 只要 while (n != 0) 和 n &= (n - 1) 两行，出错概率极小。

第二，它能体现你对二进制运算的理解层次。面试官见过太多人写逐位循环，但能写出并讲清 n & (n - 1) 的候选人明显没有那么多。这行代码就像“我会用位运算思考”的信号。

第三，它的实际性能通常更好。按位与和减法都是 CPU 的极低延迟指令，循环次数又大幅减少，尤其在稀疏二进制数上效果非常明显。我之前统计过一组协议标志位，里面大多数整数只有两三个置位，用 Kernighan 循环比逐位法快了近一个数量级。

4. 查表法与 CPU 内置指令：真实项目里的性能选择

4.1 8位查表法：四步查完 32 位

Kernighan 虽然很快，但循环次数仍然和 1 的个数相关。如果数据非常密集，全是接近全 1 的数，它的最坏情况也会退化到循环 32 次。工程上还有一类方案，时间完全固定，那就是查表法。

查表法的思路很直接：先把所有 8 位二进制数（0 到 255）的“1的个数”预先算好，存成一张表。然后要统计一个 32 位整数时，把它拆成 4 个 8 位块，每一块直接查表，最后加起来。这样无论数字多大，都只需要 4 次查表和 3 次加法。时间完全恒定，而且循环次数跟 1 的个数无关。

表怎么生成？没必要手写，可以循环生成：

table = [0] * 256 for i in range(1, 256): table[i] = table[i >> 1] + (i & 1)

这行代码用了一个简单递推：i 的二进制等于去掉最后一位再补上最后一位的判断。杀掉最低位后看 table[i >> 1]，最后一位是 0 就加 0，是 1 就加 1。一次能算出 256 个值。

有了表之后，查询代码也很规整：

def hammingWeight(n): return (table[n & 0xFF] + table[(n >> 8) & 0xFF] + table[(n >> 16) & 0xFF] + table[n >> 24])

为什么选 8 位而不是 16 位或 4 位？8 位表只要 256 个元素，占用内存很小，而且 4 次查询刚好覆盖 32 位，读写都很快。如果选 16 位表，只需 2 次查询，但表需要 65536 个元素，内存占用暴涨；如果选 4 位表，表很小但需要 8 次查询。工程上 8 位表是性价比最均衡的选择。

查表法还有一个额外好处：如果统计的是一批数据，你可以把表放在缓存友好的位置，反复使用。CPU 访问内存和查表的开销通常小于多次循环计算的累积开销。当然，表也存在内存访问延迟，数据量不是特别大的时候，它未必比 Kernighan 快。关于这点，我在后面的对比表里会展开。

4.2 内置函数其实是最省事的方案

纯粹为了解决问题，现代语言基本都提供了内置人口计数函数。Java 有 Integer.bitCount(int i)，C++ 有 __builtin_popcount，Python 3.10 以后有 int.bit_count()，Go 有 bits.OnesCount32。这些函数能直接用，不需要你自己实现。

为什么内置函数往往更快？因为现代 CPU 大多支持一条专门的 POPCNT 指令，硬件上直接算出一个整数里有多少个 1，一条指令就能完成。Java 里 Integer.bitCount 在 JVM 层面会被优化成这条 CPU 指令，C++ 的 __builtin_popcount 在支持该指令的机器上也会直接编译成 POPCNT。这是真正的 O(1) 方案，常数小到几乎可以忽略。

不过用内置函数也有注意事项。第一，旧 CPU 可能不支持 POPCNT 指令，编译器通常会在运行时检测，兼容层有额外开销。第二，Java 的 bitCount 接收 int，如果你面对的是 long，要用 Long.bitCount。第三，JavaScript 没有直接的 popcount 方法，你还是得自己写或借助逐位法。所以“看看语言有没有内置”是第一步，但不能默认所有环境都有。

4.3 五类方案横向对比

我习惯把不同方案放在一起比较，方便按场景选择。下面这个表是我自己的总结，可以当作速查表：

如果你问我在真实项目里怎么选，我的答案是：能用内置函数就用内置函数；不能用的环境下，数据稀疏用 Kernighan，数据密集用查表法。这里的稀疏和密集，指的是数据中 1 的占比。比如网络 flags 字段大多是稀疏的，Kernighan 优势明显；而位图、掩码这类经常接近全 1 的数据，查表法更稳定。

5. 扩展玩法：位1个数不只是面试题

5.1 汉明距离：异或之后再数一次1

统计“两个整数有多少个二进制位不同”也是常见问题。它的解法特别优雅：先异或，再统计异或结果里 1 的个数。因为异或操作的结果中，只有两个数不同的位才会变成 1，相同的位会变成 0。

public int hammingDistance(int x, int y) { return Integer.bitCount(x ^ y); }

一行解决。汉明距离在信息论、编码纠错、图像相似度计算里是基础概念。比如图片哈希之后算两张图的相似度，用的就是汉明距离。这个扩展题在面试中也很多见，其实就是今天这道题的“异或版”，会了位1个数，就自然会了汉明距离。

5.2 奇偶校验与布隆过滤器的底层依赖

我们平时说的奇偶校验，本质上也是在数 1：统计一个字节或一组数据里 1 的个数，如果是奇数就补一个校验位，表示“奇校验”。网络传输里常见这种机制，用来检测单比特翻转。底层实现就是 popcount，只是只关心最后是奇数还是偶数。

布隆过滤器则是把位运算用到了极致。它内部由一个很大的位数组和若干哈希函数组成。每次查询要检查多个位置是否均为 1，也就涉及对位数组区域进行读取、统计、置位。假如你要知道当前布隆过滤器已经占用了多少位（负载率），就需要统计整个位数组里 1 的个数。数据量一大，逐位查就太慢了，工程实现一般会按 64 位整型分块存储，然后批量统计。这时候选择一个高效的 popcount 实现，直接决定了系统容量预估的速度。

5.3 日常练习的避坑清单与我的个人体会

学了这么多，最后分享一份我踩过多次坑之后整理的检查清单：

• 确认输入是无符号还是有符号。无符号环境随便右移，有符号环境必须想清楚补位规则。
• Java 里区别 >> 和 >>>；C/C++ 尽量用 uint32_t 这类无符号类型，不要用 int 硬扛。
• Python 里避免直接用 while n 处理负数，固定循环次数更稳。
• 64 位数字别只查 4 个 8 位块，要查 8 个；查表法要按实际位数扩展。
• 如果用到内置函数，先查语言版本和运行环境是否真的支持硬件指令。
• 用查表法时，注意表生成代码里的边界，table[i >> 1] 一定在之前已经算好，顺序不能反。

我个人练这题时印象最深的一点是：真正值钱的不是背下某个公式，而是理解“为什么 n - 1 会让最低位的 1 变成 0”。你把这一层原理想透，二进制 2 的幂判断、汉明距离、甚至后面更复杂的位掩码操作，都会忽然变得通顺。最后再分享一个小技巧：面试时如果被要求“不能使用语言内置函数”，你可以在小本子上先写出查表法的表生成代码，再写出查询函数，这一套组合基本能覆盖所有限制条件，也最容易给面试官留下“你确实懂底层”的印象。