一、算法背景Brian Kernighan 算法是一种高效计算二进制数中 1 的个数即汉明权重Hamming Weight的技巧。相比于逐位检查的常规方法它只遍历值为 1 的位而不是所有位因此在二进制中 1 较少时尤为高效。二、核心原理算法的关键在于一个非常巧妙的位运算恒等式n (n - 1)的结果是将 n 的二进制表示中最低位的 1 变为 0。为什么对于任意非零整数nn - 1会将最右侧的 1 变为 0将该位右边的所有 0 变为 1左侧高位保持不变例如n 1010020textn 10100 n - 1 10011 n (n-1) 10000 ← 最低位的 1 被清除了因此每次执行n n - 1就能消除一个 1循环次数正好等于 1 的个数。三、代码实现int countBits(int n) { int count 0; while (n ! 0) { n (n - 1); count; } return count; }四、复杂度分析维度复杂度说明时间复杂度O(k)k 为二进制中 1 的个数远优于固定循环 32/64 次空间复杂度O(1)只使用常数个变量五、边界情况与注意事项1. 负数的处理在 Java 中有符号整数使用补码表示。Kernighan 算法使用n (n - 1)操作对负数同样有效因为n - 1在补码下仍然会将最低位的 1 变为 0该位右侧的 0 变为 1操作后该最低位的 1 被清零高位保持不变循环while (n ! 0)会在所有 1 被清除后结束包括符号位// Java 中直接使用 int包括负数完全没问题 public static int countBits(int n) { int count 0; while (n ! 0) { n (n - 1); count; } return count; } System.out.println(countBits(-1)); // 补码全1 → 32 System.out.println(countBits(-13)); // 补码中1的个数 → 302. n 0 的情况循环条件while (n ! 0)为 false直接返回 0结果正确。System.out.println(countBits(0)); // 输出 0六、相关位运算技巧表达式效果常见用途n -n提取最低位的 1lowbit树状数组Fenwick Treen ^ (n - 1)生成从最低位到第一个 1 的掩码位运算扩展n | (n - 1)将最低位的 1 之后所有位变为 1位域合并七、示例演示以n 13二进制1101为例步骤当前 nn-1n (n-1)消除的 1计数初始1101———0①110111001100最低位1②110010111000第二位2③100001110000最高位3最终count 3即1101中有 3 个 1。八、其他统计方法对比方法循环次数优点缺点逐位检查固定 32/64 次简单直观即使 1 很少也要循环所有位Kernighan等于 1 的个数高效位数越稀疏越快仍然依赖循环次数查表法分块固定次数如 4 次查表速度极快需要额外内存内置指令__builtin_popcountO(1) 硬件级最快非跨平台