刷题刷到“二进制中1的个数”这道题的时候很多人第一反应是“太简单了”但真到面试手写环节或者做牛客每日一题打卡时往往又会卡在几个隐性坑上负数右移是补1还是补0n和n-1到底发生了什么查表法的表是怎么算出来的这篇文章我不光把这道题拆透还会顺着牛客tracker的刷题思路把位运算相关的知识串成一条线让你以后再遇到这类题看一眼就能出思路。1. 题目到底在问什么拆解“二进制数1”的考点与陷阱1.1 题目本质与面试官的真实意图“二进制数1”这个标题在牛客网和各大算法题集中对应的是非常经典的一道题输入一个整数输出该数二进制表示中1的个数。比如输入9二进制是1001那么1的个数就是2输入-1在多数语言中表示成32位全1结果就是32。面试官为什么爱考这道题因为它有一个极好的梯度基础解法人人能写但进阶解法能拉开差距。它考察的不只是“你会不会用循环”更是“你懂不懂二进制本身”——补码的表示、位运算的特性、时间复杂度的优化思路。这题在牛客剑指offer系列里是高频题也是日常tracker里最适合用来反复练习位运算的入门题。1.2 关键词把这道题至少分成了三个层次从不同关键词递进的角度看“二进制数”这三个词本身就把题目划分成了三种难度阶梯第一层数二进制。这是最直观的理解用循环一位一位数满足多数人对题目的第一反应。第二层数二进制中的1。这意味着要处理负数、无符号数、溢出这些边界情况。很多人在这一层开始踩坑。第三层用二进制的特性去数。真正的高手不是“数”而是通过位运算“消”1或者用数学方法并行计数。在牛客tracker记录这道题时我是按这三层分别提交了不同版本每写一版都有新的理解。下面逐个展开讲。2. 基础解法循环位移与mask法的原理及代码2.1 逐位检查法最没有歧义的实现最直白的思路让整数和1做与运算如果结果不是0说明最低位是1计数加一然后右移一位重复这个过程直到整数变成0。用代码写就是public int hammingWeight(int n) { int count 0; while (n ! 0) { count (n 1); n n 1; // 这里是关键用无符号右移 } return count; }这里有一个非常关键的细节右移必须用无符号右移而不能用有符号右移。原因在于对于负数Java等语言的有符号右移会在高位补1导致循环永远无法结束而无符号右移高位补0最终能把数字变成0正常结束。这个版本的时间复杂度是O(log n)也就是二进制位数级别的复杂度。对于32位的int固定循环32次就可以。优点是几乎没有理解门槛适合作为第一版提交论证正确性。2.2 mask法更贴合“逐位”语义的变体有同学会问能不能不移动输入的数字而是移动一个掩码这也是常见写法public int hammingWeight(int n) { int count 0; int mask 1; for (int i 0; i 32; i) { if ((n mask) ! 0) { count; } mask 1; } return count; }这个写法的好处是彻底绕开了“右移负数”这个坑。不管是正数还是负数我们只让掩码从第0位一路移到第31位每次做与运算都不动原始数字所以不存在符号位扩散问题。很多遵循《剑指Offer》书籍老版本答案的同学或者使用C/C编程风格的人会自然倾向于这种写法。我在初学阶段也更喜欢用这个版本因为它的循环次数明确固定为32次逻辑清晰不容易出错。2.3 为什么不能直接转成字符串然后数“1”很多刚上手刷题的人会想到这种取巧方案把整数转成二进制字符串然后遍历数1的数量。在本地跑测试没问题但放在面试或在线评测中这不是一个值得推荐的方案。原因有三一是转换字符串涉及额外内存分配在追求时间复杂度和空间复杂度的算法题里不优雅二是在面试中面试官让你写这题就是想看位运算功底你写个Integer.toBinaryString(n)基本等于告诉对方“我不懂底层实现”三是面试追问环节只要问一句“超过32位的长整数怎么处理转换字符串还会快吗”你很容易答不上来。所以既然刷题就一步到位练位运算的思考方式。3. 进阶思路n (n-1) 的数学原理与配套实现3.1 一个公式消掉一个1核心原理推演真正让这道题从“基础题”变成“经典题”的是n (n-1)这个操作。很多人知道这个公式能消掉最低位的1但很多人不知道它“为什么能”。我用一个具体例子来拆解。假设n 12二进制是1100那么n - 1 11二进制是1011。这时观察n 1100 n - 1 1011 n (n-1) 1000发生了什么n - 1的时候由于最低位的1后面全是0减去1就会向这个最低位的1借位相当于把这个1变成0同时它右边的所有0全部变成1。比如12的最低位1在第2位从第0位开始数它右边的两个0就变成了1。此时再做与运算原本最低位1右边的0在n-1中已经变成1了1和0与运算得0原本最低位1自己的位置n中是1n-1中是0与运算也得0。只有更高位的1保持不变与运算后还是1。所以结论就是n (n-1)能够把n的二进制表示中最低位那个1清零其余位保持不变。3.2 循环消1法让循环次数等于1的个数基于这个原理我们就可以让循环次数不再固定为32次而是“有几个1就跑几次”public int hammingWeight(int n) { int count 0; while (n ! 0) { n n (n - 1); count; } return count; }这个版本对负数也很安全因为负数在Java中同样遵循补码运算规则n - 1在二进制层面依然会产生借位依然能消掉最低位的1。比如n -1二进制全1每次消掉一个1循环32次后归0结果返回32。这个写法的优雅之处在于它不关心数字的位数上限循环次数严格等于有效1的个数。时间复杂度可以估算为O(k)其中k是1的个数最坏情况依旧O(32)。在面试中这是最受青睐的解法也是许多面试官真正想听到的方案。3.3 在牛客tracker中如何沉淀这个解法我会建议在牛客的做题记录里为这道题建两条记录一条记录“逐位检查法”标注为“最易理解、无符号移位是关键”一条记录“n(n-1)法”标注为“最优解、理解消1原理”。后续复习时优先看第二条大脑能很快把公式和原理重新激活。这类题目的记忆重点不是代码而是那个“为什么”。只要你能在草稿纸上画出1100和1011相与的过程就算过了一个月再遇到这题也能顺手写出来。4. 还能更快吗查表法与分治法到底强在哪4.1 空间换时间静态表查8位块当面试官追问“还有没有更快的方法”时查表法是一个很自然的进阶思路。以8位为一个块先把0到255这256个数字的“1的个数”存成数组然后将32位int拆成4个8位段分别查表再相加。public class Solution { private static final int[] BIT_COUNT_TABLE new int[256]; static { for (int i 1; i 256; i) { BIT_COUNT_TABLE[i] BIT_COUNT_TABLE[i 1] (i 1); } } public int hammingWeight(int n) { return BIT_COUNT_TABLE[n 0xFF] BIT_COUNT_TABLE[(n 8) 0xFF] BIT_COUNT_TABLE[(n 16) 0xFF] BIT_COUNT_TABLE[(n 24) 0xFF]; } }这里的预处理表用了一个DP关系数字i的1的个数等于i去掉最低位后右移一位的1的个数再加上最低位本身i 1。这个预处理巧妙地复用了递推思想而且只在静态初始化时执行一次。这个解法每次统计只需要4次查表加上3次移位操作时间复杂度是O(1)性能非常稳定并且空间只占256个int约1KB左右完全可接受。这种方式特别适合你需要对海量整数频繁执行“统计1的个数”的场景典型如海量数据校验、某些哈希算法辅助运算等。4.2 分治法用位运算同时处理32位如果面试官继续深挖“如果你不想用额外空间呢”就到了分治法登场的时候。这里要介绍的就是经典的SWARSIMD Within A Register算法中文常叫“寄存器内并行计算”核心思路是两两合并计数。直接上代码这个实现你甚至可以背下来public int hammingWeightBySwar(int n) { n n - ((n 1) 0x55555555); n (n 0x33333333) ((n 2) 0x33333333); n (n (n 4)) 0x0F0F0F0F; n n (n 8); n n (n 16); return n 0x3F; }一眼看上去很吓人但拆开看每一行都只做一件事不断把相邻的位、相邻的块合并计算数量。以第一行为例0x55555555的二进制是0101...0101也就是每两位的奇数位为1。n 1相当于把所有位向右移动一位再与0x55555555做与运算得到的是原本偶数位的信息。然后n减去这个结果实际上是在每两个比特位内部完成了“一个两位二进制数中1的个数”的计数结果存回这两位中。到第二行时每4位为一组通过两次掩码加移位把上下两个2位子结果相加得到每4位内的1的个数。第三行再做一次变成每8位一组。最后两行用移位加法把32位内部的计数全部汇合到最低的8位中最终n 0x3F0x3F等于63取出最终值。这个算法的常数级高效没有分支跳转在一些底层库如Java的Integer.bitCount()中就有类似实现。作为面试中的“终极加分项”不需要现场完整推导但能清晰说明每一行的目的已经足够让面试官眼前一亮。4.3 三种高阶段方案的对照选择方法时间复杂度空间复杂度适用场景推荐场景逐位检查法O(32)O(1)初次入门入门教学n (n-1)O(k)k为1的个数O(1)最均衡面试手写首选查表法O(1)O(256)高频重复统计工程落地SWAR分治法O(1)O(1)极限性能源码级优化实际工程中查表法已经足够快只有在极致性能要求的底层库中才会去使用SWAR这类并行计数方案。5. 实战复盘常见错误榜、边界测试与一题多解延伸5.1 这些坑我踩过请避雷我最早刷这道题时用的是C语言思维直接写了n n 1在牛客上死活通不过后来才发现是负数死循环的问题。所以我把常见问题整理成了一份自查清单你们可以直接对照排查。错误一用有符号右移处理负数这是最经典的高频错误。n -1时二进制是32个1用右移后最高位持续补1n永远不等于0循环直接超时。解决方案就是使用无符号右移或者在循环前先把n转成long类型并用 0xFFFFFFFFL截断为无符号语义。错误二误以为整数没有位数上限很多刚学编程的同学会写while (n 0)来遍历这忽略了n是负数时根本进不了循环。正确姿势是while (n ! 0)才符合位运算语义。错误三查表法的表算错少部分同学选择手动写252项的静态表经常抄错。我更推荐用DP方式预处理生成也就是用BIT_COUNT_TABLE[i] BIT_COUNT_TABLE[i 1] (i 1)不容易错代码还简洁。错误四过度使用位运算但看不清逻辑有人为了炫技一口气把SWAR的每一步压缩成一行结果自己过两天都看不懂了。阶段不同写法不同学习阶段优先清晰和正确工作阶段才追求极致性能。5.2 如何针对这道题做边界测试牛客刷题有一个好习惯提交前先把边界测试自己跑一遍。这道题我总结了几个关键测试用例你们可以记下来输入n二进制简写期望输出备注000全0边界111最小正数2101单个1左移3112最低两位都是12558个188位全满0x7FFFFFFF31个131最大正数0x800000001000...01最小负数/最高位为1-132个132全1负数把这几组用例跑通了代码的正确性基本就有保障。5.3 一题多解的“举一反三”路线这题的价值不仅在于本身更在于它能延伸出一串题目延伸一统计两个整数二进制位不同的个数。先用异或把不同的位变成1再统计结果中1的个数调用的就是本题的代码。这是LeetCode 461汉明距离的原型。延伸二判断整数是否为2的幂。一个正整数如果是2的幂那么它的二进制表示只有1个1。于是可以直接用n 0 (n (n - 1)) 0来判断一行搞定。延伸三找到一个数字变成0需要消掉多少个1。很多题会用到“循环消1”的思想比如某些算法需要记录二进制操作步数本质上就是对同一个公式的应用。如果可以我建议你把这些延伸题也加进牛客tracker每做一道都在备注里加上“关联原题”。这样你的刷题记录就不再是孤立的题目列表而是一张以“位运算”为主干的复习知识图谱。面试前集中过一遍效率比重新刷几十道题高得多。6. 刷题之外位运算在真实工程里的用武之地6.1 权限系统与状态标记很多业务系统里位运算不是考试专用而是真实存在的高效方案。经典例子是权限管理用整数每一位代表一个权限项读权限是1写权限是2删除权限是4这种设计下“一个整数的二进制位上有几个1”直接对应“这个角色分配了几项权限”。此时题目里的n (n - 1)技巧就可以用来快速统计某个角色分配的权限数量或者快速清除某个权限位。相比使用独立的权限表存多条记录位标记的方式查询效率极高内存占用极小。6.2 布隆过滤器与哈希相关场景布隆过滤器内部就是个大位数组插入元素时往往要设置多个位为1判断元素是否存在时则要检查这些位是否都为1。此时“统计一个位数组中有多少位为1”直接关系到元素数量和误判率的估算。在实现布隆过滤器时需要用到一个二进制块中1的个数的函数思路正是本题的查表法或SWAR法。所以在工作中如果你被安排实现一个低层工具类很可能会发现Integer.bitCount()这类底层API不完全够用——比如要统计一段连续内存区域、而不是单个int的1的个数——这时候掌握查表法和分治法的扩展写法就非常有价值。6.3 哈希函数与数据校验的加速部分哈希算法在计算摘要时会使用二进制位运算作为核心步骤如计算一个64位整数的汉明重量用于随机性检验。类似场景中一个高效统计二进制中1个数的函数能显著减少计算耗时。这也是为什么Integer.bitCount()在JDK中一直保持着相当优化的实现方案理解了SWAR方法后再看JDK源码你会觉得熟悉许多。7. 复盘与刷题方法沉淀这道“二进制数1”作为经典题目我建议在牛客tracker中至少保存两版代码、一组测试用例和一篇自己的做题笔记。笔记不用写长篇大论记录几个关键词即可无符号右移、n(n-1)消1原理、查表预处理、SWAR并行计数。我自己刷题实践中的一点体会像这种题与其刷三遍不如彻底深挖一遍。把最基础的移位写法做到肌肉记忆把消1思路理解到能推导的程度把进阶方案做到能说出复杂度差异这样哪怕面试官从这道题发散成“汉明距离”“2的幂判断”“权限位计算”你都能从容接住。如果后续想继续深挖位运算方向建议按“异或应用 → 数位DP → 求子集 → 状态压缩DP”的顺序推进每一步都会碰到这道题的影子。把基础题目吃透后面的路会顺很多。