1. 项目概述从一道经典面试题说起“请写一个函数输入一个整数输出该数二进制表示中1的个数。” 这道题但凡你刷过LeetCode、牛客网或者参加过任何一场技术面试大概率都遇到过。它就像算法世界的“Hello World”看似简单却暗藏玄机是检验一个程序员对计算机底层、位运算以及编程思维理解深度的绝佳试金石。我当年第一次在面试中被问到这道题时下意识地就想到了“除2取余”法结果被面试官追问了时间和空间复杂度以及是否有更优解当场就有点懵。后来在无数次的刷题和实际项目优化中我才真正体会到这道题背后串联的是从最基础的数学逻辑到最高效的位运算技巧的完整知识链。今天我们就以C为例抛开那些花哨的框架和库回归到最本质的0和1的世界把这道题里里外外、从笨办法到巧办法彻底讲透。无论你是正在备战秋招的学生还是希望夯实基础的在职工程师这篇文章都将带你重新认识这个“老朋友”并让你在下次被问及时能从容地给出至少三种解法并清晰地说出各自的优劣。2. 核心需求与问题本质解析2.1 问题定义与输入输出边界题目要求非常明确给定一个整数在C中我们通常考虑int类型返回其二进制表示形式中‘1’位的数量。这个数量在计算机科学中有一个专门的术语——Population Count或Hamming Weight。首先我们必须明确几个关键边界这些是写出健壮代码的前提整数类型通常指有符号32位整数(int32_t)。在C中int的具体位数由编译器和平台决定通常是32位但为了严谨我们可以使用std::int32_t需要cstdint头文件。负数处理这是本题的第一个陷阱。整数在内存中以二进制补码形式存储。例如-1在32位系统中表示为0xFFFFFFFF全1其1的个数是32。我们的算法必须能正确处理负数。输入范围对于32位有符号整数输入范围是[-2^31, 2^31-1]。算法需要覆盖整个范围。2.2 从数学方法到计算机思维的转变最直观的解法来源于我们小学就学过的“进制转换”将一个十进制数不断除以2记录余数直到商为0。余数序列的逆序就是二进制表示其中1的个数就是余数为1的次数。int countBits_Naive(int n) { int count 0; while (n ! 0) { if (n % 2 ! 0) { // 或者 if (n 1) count; } n n / 2; // 等价于 n 1但对于负数有区别 } return count; }注意这个方法对于正整数是有效的。但对于负数n n / 2和n 1算术右移在C/C中的行为是不同的。除法向零取整而算术右移会保持符号位。对于负数n / 2最终会得到0从而结束循环但这并没有遍历其补码表示的所有位因此结果是错误的。这是我们遇到的第一个坑。所以我们需要将思维从“数学除法”转换到“计算机位操作”。我们不应该关心这个数的数学值如何变化而应该直接将其视为一个固定长度的二进制位序列然后检查其中每一位。这就引出了我们的第一种可靠解法。3. 核心解法深度剖析与C实现3.1 解法一逐位检查法使用无符号类型或固定移位为了解决负数问题一个核心技巧是使用无符号整数来接收或转换我们的输入。这样右移操作就会变成逻辑右移高位补0而不是算术右移高位补符号位。思路将输入整数转换为无符号数。准备一个掩码mask初始值为1二进制...0001。在循环中将无符号数与掩码进行按位与操作如果结果不为0则说明最低位是1计数器加1。然后将掩码左移一位mask 1检查下一位。重复直到检查完所有位例如32次。#include cstdint // 为了使用固定宽度整数类型 int hammingWeight_ShiftMask(uint32_t n) { // 参数直接使用uint32_t int count 0; uint32_t mask 1; for (int i 0; i 32; i) { if ((n mask) ! 0) { count; } mask 1; } return count; } // 调用时如果需要处理int可以这样转换 int num -1; int result hammingWeight_ShiftMask(static_castuint32_t(num));另一种等价的逐位检查法是固定移动输入数本身而不是移动掩码。这种方法更常见。int hammingWeight_ShiftInput(int n) { int count 0; unsigned int un n; // 关键转换为无符号数确保右移是逻辑右移 while (un ! 0) { if (un 1) { // 检查最低位 count; } un 1; // 逻辑右移 } return count; }复杂度分析时间复杂度O(k)k是整数的位数例如32。无论数字大小都要循环固定的32次。空间复杂度O(1)只使用了几个固定变量。优点逻辑极其清晰易于理解和实现能正确处理负数。缺点循环次数固定即使对于很小的数如1二进制...0001也需要检查所有32位效率不是最优。3.2 解法二n (n-1)魔法技巧这是面试官最期望看到的解法因为它巧妙利用了二进制运算的一个特性能将时间复杂度优化到只与数字中1的个数相关。核心原理对于一个整数n运算n (n-1)的结果会把n的二进制表示中最低位的1变成0。让我们举个例子假设n 12二进制为1100。n - 1 11二进制为1011。n (n-1) 1100 1011 1000。 可以看到原来n中最低位的1从右数第3位被消除了。再迭代一次n 1000(8),n-1 0111(7)。n (n-1) 1000 0111 0000。 迭代停止。我们进行了2次操作正好是12的二进制中1的个数。C实现int hammingWeight_BrianKernighan(int n) { int count 0; unsigned int un n; // 同样转换为无符号确保减法溢出等行为符合预期 while (un ! 0) { un (un - 1); // 消除最低位的1 count; } return count; }复杂度分析时间复杂度O(m)其中m是整数n的二进制表示中1的个数。对于1很少的数如2的幂只有一个1只需一次循环。这比固定32次的循环优秀得多。空间复杂度O(1)。优点效率高代码简洁是位运算技巧的经典体现。缺点原理需要稍加理解对初学者不够直观。实操心得n (n-1)这个技巧必须刻在脑子里。它不仅是解决“二进制中1的个数”的关键还是解决其他一系列位操作问题的核心技巧例如判断一个数是否是2的幂n 0 (n (n-1)) 0。计算两个整数的汉明距离先异或再计算异或结果中1的个数。3.3 解法三查表法Table Lookup与分治思想当追求极致性能或者需要处理大量数据时查表法是一个选择。其思想是“空间换时间”预先计算好所有可能的小数据块例如8位中1的个数存储在一个数组中。然后对于一个32位数将其拆分成4个8位块分别查表并累加结果。步骤建表创建一个大小为2562^8的数组tabletable[i]存储字节i0-255中1的个数。拆分与查表将32位无符号整数n解释为4个字节。通过移位和掩码操作依次取出这4个字节的值作为索引去查表累加结果。C实现int hammingWeight_LookupTable(uint32_t n) { // 静态表只需初始化一次 static const unsigned char table[256] { #define B2(n) n, n1, n1, n2 #define B4(n) B2(n), B2(n1), B2(n1), B2(n2) #define B6(n) B4(n), B4(n1), B4(n1), B4(n2) B6(0), B6(1), B6(1), B6(2) }; // 分别查4个字节 unsigned char* p (unsigned char*)n; return table[p[0]] table[p[1]] table[p[2]] table[p[3]]; }上面的建表代码使用了一个巧妙的宏展开来生成表其本质是动态规划思想一个字节中1的个数等于其高半字节和低半字节中1的个数之和。复杂度分析时间复杂度O(1)仅进行几次固定次数的内存访问和加法运算。空间复杂度O(256)需要一个256字节的查找表。优点在需要反复调用该函数的场景下速度极快。缺点占用额外内存代码可读性稍差且性能优势在现代CPU的缓存和指令集优化下可能不那么明显。3.4 解法四利用编译器内置函数或标准库在实际工程中我们通常不重复造轮子。许多编译器和标准库提供了计算Population Count的高效实现。GCC/Clang内置函数__builtin_popcount(unsigned int n)。这个函数会被编译器翻译为底层最高效的机器指令如x86的POPCNT指令。C20标准库bit头文件提供了std::popcount(T n)函数模板。// 方法1使用GCC/Clang内置函数 int hammingWeight_Builtin(int n) { return __builtin_popcount(static_castunsigned int(n)); } // 方法2使用C20标准库 (需要编译器支持-stdc20) #include bit int hammingWeight_STL(int n) { return std::popcount(static_castuint32_t(n)); }这是生产环境的首选方法因为它简洁、高效、正确。4. 性能对比与场景选择我们编写一个简单的测试程序在循环中调用上述不同方法数百万次来直观感受性能差异结果因机器和编译器优化而异但相对关系有参考价值。方法时间复杂度空间复杂度优点缺点适用场景逐位检查O(32)O(1)逻辑简单绝对稳定循环次数固定效率非最优教学、理解原理、对性能不敏感的简单场景n (n-1)O(1的个数)O(1)效率高技巧经典原理需理解面试首选、常规代码优化、中等性能要求查表法O(1)O(256)理论速度最快占用内存代码稍复杂极致性能优化、嵌入式系统如果内存允许、处理海量数据内置/标准库O(1)O(1)最简单效率最高硬件指令依赖编译器和标准生产代码绝对首选、任何需要此功能的实际项目注意事项性能测试时务必关闭编译器优化进行对比否则编译器可能会将简单的循环优化到和内联函数一样快。在实际开启优化(-O2)后内置函数和查表法的优势会非常明显因为它们直接对应或逼近单条CPU指令。5. 相关扩展问题与实战应用掌握了核心解法我们可以轻松应对一些变种问题这也是面试中常见的追问环节。5.1 扩展问题一判断一个整数是否是2的幂问题不使用循环/递归判断一个整数是否是2的幂如1, 2, 4, 8...。解法利用n (n-1)。2的幂的二进制表示中只有一位是1。因此对于正整数n如果n (n-1) 0那么它就是2的幂。需要额外判断n 0因为0也满足这个等式但不是2的幂。bool isPowerOfTwo(int n) { return n 0 (n (n - 1)) 0; }5.2 扩展问题二计算两个整数的汉明距离问题汉明距离是指两个等长字符串或数字在对应位置上不同字符或位的个数。对于整数就是其二进制表示中对应位不同的数量。解法先对两个数进行异或操作x ^ y异或结果为1的位就是原数不同的位。然后问题就转化为了计算异或结果中1的个数。int hammingDistance(int x, int y) { return hammingWeight_BrianKernighan(x ^ y); // 可以用任意一种方法实现 }5.3 实战应用场景位图Bitmap与布隆过滤器Bloom Filter在这些数据结构中我们经常需要快速统计特定位区间中1的个数或者判断某一位的状态。popcount是基础操作。信息检索与相似度计算在计算文档的SimHash或处理特征向量时汉明距离是衡量相似度的常用指标其核心就是计算1的个数。游戏开发与状态压缩许多棋盘类游戏如围棋、黑白棋的状态可以用位棋盘表示快速计算棋盘上的棋子数1的个数对于评估局面至关重要。密码学与纠错码一些加密算法和纠错码如奇偶校验、汉明码需要计算数据中1的奇偶性或数量。6. 常见“坑点”与调试技巧实录即使理解了算法实现时也可能掉进一些坑里。下面是我和同事们在实际编码和面试中总结的几个常见问题。6.1 坑点一负数的右移与循环终止这是最大的一个坑前面已经提到。永远记住在C/C中对有符号整数进行右移是算术右移符号位会被保留并填充到高位。这会导致对于负数使用while (n) { ... n 1; }的循环可能无法终止如果符号位一直是1或者无法正确统计所有位。解决方案在操作前先将输入转换为无符号类型unsigned int。6.2 坑点二运算符优先级位运算符的优先级通常低于比较运算符。例如在写判断条件时if (n 1 1) { ... } // 错误因为的优先级高于所以这行代码实际等价于if (n (1 1))即if (n 1)虽然在这个特例里结果巧合正确但逻辑混乱且危险。解决方案给位运算加上括号这是一个良好的编程习惯。if ((n 1) 1) { ... } // 正确且清晰6.3 坑点三忽略整数宽度在查表法或需要精确位操作时使用int可能导致不可移植。在32位平台上是32位在64位平台可能是64位。解决方案使用固定宽度的整数类型如uint32_t、uint64_t定义在cstdint中。6.4 调试技巧打印二进制表示当你的算法结果不符合预期时最直接的调试方法就是把整数的二进制形式打印出来看看。#include bitset #include iostream void printBinary(int n) { std::cout std::bitset32(n) std::endl; // 打印32位表示 } // 或者自己实现一个简单的 void printBinarySimple(unsigned int n) { for (int i 31; i 0; --i) { std::cout ((n i) 1); if (i % 4 0) std::cout ; // 每4位加个空格方便阅读 } std::cout std::endl; }这个小工具能帮你直观地验证输入和中间步骤对于理解位运算非常有帮助。7. 从这道题延伸出的学习路径一道简单的“二进制中1的个数”其实是一扇通往计算机系统基础的大门。如果你对此感兴趣我建议可以沿着以下路径深入学习深入位运算掌握与、或|、异或^、非~、左移、右移的所有常用技巧如设置位、清除位、切换位、检测位等。理解原码、反码、补码这是计算机表示有符号整数的基石理解了它你才能明白为什么-1 0xFF的结果是0xFF以及算术右移和逻辑右移的根本区别。学习更多的“魔法”位操作比如不用临时变量交换两个数a ^ b; b ^ a; a ^ b;快速判断奇偶快速乘除2的幂等。探索CPU指令集了解像POPCNTPopulation Count这样的专用指令理解编译器内置函数是如何映射到这些高效指令的这能让你写出更贴近机器效率的代码。应用到具体算法和数据结构学习位图、布隆过滤器、状态压缩动态规划等高级主题你会发现位运算在这些领域能发挥出惊人的空间和时间效率。回到开头下次面试再遇到这道题你可以从容地从最基础的逐位检查讲起然后引出高效的n (n-1)技巧再提到查表法和内置函数并对比它们的优劣。如果能再聊一两个相关的扩展问题和应用场景面试官对你的基础扎实程度和知识广度一定会留下深刻印象。刷题不只是为了记住答案更是为了构建起这种由点及面、融会贯通的知识网络。这道关于0和1的小题值得你花时间把它彻底吃透。