ccf41-A 平衡数（balance）

题目

题目描述

对于一个正整数 a ，如果其二进制表示中 1 和 0 的个数相等，则称其为平衡数。
这里的二进制表示以 1 为最高位，即不考虑更高位用于补位的 0 。例如，正整数 12 的二进制表示为 1100 ，包含两个 1 和两个 0。在实际存储中，更高位可能需要填 0 补位，如 00001100，在本题中无需考虑此种情况。

小 P 已经生成好了 $n$ 个正整数： $a_1, a_2, a_3, \ldots, a_n$ ,试编程统计里面有多少个平衡数。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 $n$ ，第二行包含空格分隔的 $n$ 个正整数 $a_1, a_2, a_3, \ldots, a_n$

输出格式

输出到标准输出。

输出一个整数，表示 $a_1, a_2, a_3, \ldots, a_n$ 中平衡数的个数。

样例输入

1
2

3
2 5 9

样例输出

样例解释

2 的二进制表示为 10，是平衡数；

5 的二进制表示为 101，不是平衡数；

9 的二进制表示为 1001，是平衡数。

子任务

$50%$ 的测试点满足： $0 < a_i \leq 256$

全部的测试点满足： $0 < n \leq 100 \quad \text{且} \quad 0 < a_i \leq 10^{9}$

题解

核心代码：

int bits = 0, ones = 0;
while (a > 0) {
    if (a & 1) ++ones;   // 检查最低位是否为 1
    ++bits;              // 每处理一位，总位数加 1
    a >>= 1;             // 右移一位，丢掉已经处理的最低位
}
if (ones * 2 == bits)    // 平衡数判断
    ++cnt;

核心考察点：

二进制表示：理解正整数的二进制形式（最高位为1，无前导零）。
位运算：使用 & 和右移 >> 逐位统计1的个数。
循环与条件判断：统计二进制总位数和1的个数，判断是否满足 1的个数 == 0的个数（等价于 2 × 1的个数 == 总位数）

对于一个正整数，其二进制表示没有前导零，即最高位一定是 1。例如 a = 13，二进制 1101，有 4 位。我们想统计：

ones：二进制中 1 的个数。
bits：二进制总共的位数（也就是最高位所在的位置数）。

整数在内存中是以二进制存储的。最低位（最右边的那一位）的值可以通过按位与 & 1 得到：

a & 1：因为 1 的二进制是 …0001，只有最低位是 1，其他位是 0。按位与操作后，结果只有最低位保留了 a 原来的值。

如果 a 最低位是 1，a & 1 等于 1（条件为真）。
如果 a 最低位是 0，a & 1 等于 0（条件为假）。
所以 if (a & 1) 就是判断当前最低位是否为 1，若是则增加 ones 计数器。

一旦处理完最低位，我们需要把它“丢掉”，让原来的次低位变成新的最低位。这通过右移一位 a >>= 1 实现：

右移操作将二进制位整体向右移动，最低位被舍弃，最高位补 0。
例如 13 → 1101，右移一位变为 110（即整数 6），原来的次低位 0 现在变成了最低位。

同时，因为处理了一位，总位数 bits 加 1。

循环条件是 while (a > 0)。当 a 变为 0 时，意味着所有的有效二进制位都已经处理完毕（最高位的 1 也被右移掉了）。此时：

bits 记录的就是原始二进制表示的总位数（不含前导零）。
ones 记录的就是其中 1 的个数。

code

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        int bits = 0, ones = 0;
        while (a > 0) {
            if (a & 1) ++ones;
            ++bits;
            a >>= 1;
        }
        if (ones * 2 == bits) ++cnt;
    }
    cout << cnt << endl;
    return 0;
}