NOIP 普及组初赛 · NOIP 2018 普及组初赛试题 第 14 题

为了统计一个非负整数的二进制形式中 $1$ 的个数，代码如下：

int CountBit(int x)
{
	int ret = 0;
	while (x)
	{
		ret++;
		___________;
	}
	return ret;
}

则空格内要填入的语句是（ ）。

这题考位运算里数二进制1个数的经典技巧。拿到题先想：循环里 ret++ 后必须消掉一个1，否则死循环。直接代入 x&=x-1 试一下，发现每轮正好抹掉最低位的1，循环次数就是1的个数，这就是 Brian Kernighan 算法。

学生容易把统计1的个数和统计位数搞混，看到右移就选 A；或者没意识到 C、D 会让 x 变大导致死循环，只盯着 B 的语法像而忽略逻辑；还有人记混位运算公式，把 x&(x-1) 和 x&(-x) 搞反，导致在树状数组或判2的幂时出错。

考点与命题视角

本题属于“进制与编码”中的位运算技巧，核心是Brian Kernighan 算法：每次用 x & (x-1) 把最低位的 1 消掉，循环次数即为 1 的个数。命题人常在这里挖坑：四个选项全是位运算，A 是右移（统计位数），C 是制造更多 1（死循环），D 是左移（死循环），只有 B 符合“消 1”的逻辑。学生若只背公式不代入验证，很容易误选。

逐空推演（以 x=5 为例）

原代码框架：

int CountBit(int x)
{
    int ret = 0;
    while (x)
    {
        ret++;
        _____________;
    }
    return ret;
}

目标：让 ret 最终等于二进制中 1 的个数。while(x) 保证循环在 x 变为 0 时终止，因此每轮必须至少消掉一个 1，否则 x 永远不为 0，程序卡死。

代入选项验证

• A. x >>= 1：右移一位，5(101) → 2(010) → 1(001) → 0，共 3 次循环，ret=3，但 5 的二进制只有 2 个 1，错误。
• B. x &= x - 1：5(101) & 4(100) = 4，下一轮 4 & 3 = 0，共 2 次循环，ret=2，正确。
• C. x |= x >> 1：5(101) | 2(010) = 7(111)，1 的个数反而增加，循环永不停止，死循环。
• D. x <<= 1：左移让数越来越大，显然死循环。

只有 B 能让每轮减少一个 1，循环次数恰好等于 1 的个数。