在计算二进制中1的个数时,变量 `v` 通常表示输入的整数,其值可以是正数或负数(以补码形式存储)。计算 `v` 的具体方法如下:
一、基本思路
通过 按位与运算来移除二进制表示中的最后一个 `1`,每执行一次 `v & (v - 1)` 操作,`v` 的二进制表示中就会减少一个 `1`。重复此操作直到 `v` 变为 `0`,统计操作次数即为 `1` 的个数。
二、步骤说明
初始化
将输入的整数赋值给变量 `v`。对于负数,需注意其以补码形式存储。
循环移除末尾 `1`
使用 `v & (v - 1)` 计算:
- `v - 1` 会将 `v` 的最低位的 `1` 变为 `0`,并使其右边的所有位取反(例如 `11001` 变为 `11000`);
- `v & (v - 1)` 结果会移除最低位的 `1`(如 `11000`)。
计数与终止条件
- 每执行一次上述操作,计数器加 `1`;
- 当 `v` 变为 `0` 时,停止循环,计数器的值即为二进制中 `1` 的个数。
三、示例
以 `v = 11010`(十进制为 `26`)为例:
初始状态:`v = 11010`(1个 `1`)
第一次操作:`v & (v - 1) = 11000`(移除最后一个 `1`)
第二次操作:`v & (v - 1) = 10100`(再移除一个 `1`)
第三次操作:`v & (v - 1) = 10000`(继续移除)
最终 `v = 0`,计数为 `3`,即二进制中有 `3` 个 `1`。
四、注意事项
该方法适用于所有整数,包括负数,因为补码表示能正确处理负数的二进制运算;
时间复杂度为 `O(k)`,其中 `k` 是二进制中 `1` 的个数,效率较高。
通过上述方法,可以高效地计算出任意整数二进制表示中 `1` 的个数。