NOIP 普及 2018 第一轮 第 14 题：用位运算统计二进制中 1 的个数

题目

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

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

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

选项

• A. x >>= 1
• B. x &= x - 1
• C. x |= x >> 1
• D. x <<= 1

答案

B

题解

考点定位

本题考「popcount 实现」,对应大纲 2.1.2 位运算（难度【1】）。

解题过程

x &= x - 1 清除最低位的 1，循环次数 = 1 的个数（更快）；x >>= 1 也可但慢一倍。

选 B。

易错提醒

① x&(x−1) 是「Brian Kernighan 算法」核心；② ret++ 在循环内 ⇒ 循环次数 = 1 的个数。