NOIP 提高组初赛 · NOIP 2018 提高组初赛试题 第 10 题

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

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

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

别一上来就右移，先想怎么让循环次数直接等于1的个数——用 x &= x - 1 每次消掉最低位的 1，循环次数自然就是答案。

最容易掉进 x >>= 1 的坑，因为右移后还得判断末位是否为 1，多写判断语句，代码变长且容易漏判。还有人选 x |= x >> 1，那是计算 1 的个数翻倍用的，跟本题无关。

考点概念：位运算统计 1 的个数

这道题考的是二进制位运算里一个非常经典的小技巧：用 x &= x - 1 能直接把当前二进制数中最低位的 1 抹掉。比如 x = 10100（20），x - 1 = 10011，两者按位与得到 10000，最低位的 1 消失了；再执行一次，10000 & 01111 = 00000，又少了一个 1。循环里每执行一次这个操作，就代表遇到一个 1，所以循环次数正好等于 1 的个数。

命题视角：为什么选这个？

命题人想考察你对位运算本质的理解，而不是死记硬背。很多初学者看到统计 1 的个数，第一反应是右移 x >>= 1 然后检查最低位 x & 1，这样代码确实能跑通，但循环次数等于二进制总位数，而不是 1 的个数，还得额外加判断逻辑，代码变长且容易出错。题目故意把 x >>= 1 放在选项 A，就是为了看你是否真的懂 x &= x - 1 这个技巧。