【面试】二进制妙用

思路：将 x 转化为二进制，看其中含有的 1 的个数。
假定 x = 6，答案为 2；假定 x = 9999，答案为 8。

1. 二进制与位运算基础

在计算机内部，整数以二进制补码形式存储。每一位（bit）只能是 0 或 1，统计 1 的个数本质上是对位的遍历。常见的做法有：

方法	代码示例	时间复杂度	备注
循环右移	`while (x) { cnt += x & 1; x >>= 1; }`	O(bit‑width)	需要遍历所有位，即使高位为 0 也会进行一次判断。
查表法	预先生成 0~255 的 1 的个数表，按字节查表	O(bit‑width/8)	适用于频繁统计的场景，空间换时间。
Brian Kernighan 算法（本文代码）	`x = x & (x-1)`	O(k)（k 为 1 的个数）	只遍历 `1` 所在的位，效率最高。

Brian Kernighan 算法的核心在于：x & (x-1) 会把 x 最低位的 1 清零，其他位保持不变。于是每一次循环都能消除一个 1，循环次数恰好等于 1 的数量。

行号	代码	解释
1	`int func( x )`	函数声明，参数 `x` 为待统计的整数。未显式指定类型，默认是 `int`（在 C89/90 中允许）。
2	`{`	函数体开始。
3	`int countx = 0;`	初始化计数器 `countx` 为 0，用于累计 `1` 的个数。
4	`while(x)`	当 `x` 不为 0 时进入循环。`x` 为 0 表示所有 `1` 已被清除，循环结束。
5	`{`	循环体开始。
6	`countx ++;`	每次循环都说明当前 `x` 中仍然至少有一个 `1`，计数器加 1。
7	`x = x&(x-1);`	关键语句：`x-1` 会把最低位的 `1` 变为 `0`，其右侧的所有 `0` 变为 `1`；随后与原 `x` 按位与，等价于把最低位的 `1` 清零。
8	`}`	循环体结束。
9	`return countx;`	返回统计结果。
10	`}`	函数结束。

步骤	x (十进制)	x (二进制)	countx
初始	6	110	0
第 1 次	`6 & 5 = 4`	100	1
第 2 次	`4 & 3 = 0`	000	2
结束	0	000	2

最终返回 2，对应二进制中两个 1。

时间复杂度：O(k)，其中 k 为 x 中 1 的个数。最坏情况（如 x = -1 在 32 位系统中为 0xFFFFFFFF）k = 32，循环 32 次；在实际使用中，k 通常远小于位宽，表现出极佳的线性效率。
空间复杂度：O(1)，仅使用了常数级别的额外变量 countx。

相比逐位右移的 O(bit‑width)，此算法在 k << bit‑width 时优势显著。

情形	说明	处理方式
`x = 0`	没有 `1`，循环体不执行，返回 0。	正常返回 0。
负数（补码）	在有符号整数中，负数的最高位为 1，且补码表示会导致 `1` 的数量可能很大。	若仅统计绝对值的 `1`，应先取 `abs(x)`；若统计完整补码位，则算法仍然有效。
`int` 长度不同	在 16、32、64 位平台上，`int` 位宽不同，循环次数随位宽变化。	代码本身不依赖位宽，仍然正确。
编译器优化	某些编译器会将此模式识别为内置函数 `__builtin_popcount`（GCC/Clang）或 `_mm_popcnt_u32`（MSVC），直接生成 POPCNT 指令。	在性能关键路径可显式使用对应内置函数或汇编指令，以获得更高效实现。

现代编译器提供了 popcount（population count）指令或库函数：