平衡数

形式化题目

给定 $n$ 个正整数 $a_1,a_2,\dots,a_n$ 。称一个正整数是平衡数，当且仅当它的二进制表示中 1 与 0 的个数相等。这里二进制表示以最高位的 1 为起点，不考虑更高位补位的 0。统计 $n$ 个数中平衡数的个数。

思路

统计一个数的二进制位

不断取出当前数的最低位：最低位为 1 就累加 ones，否则累加 zeros，然后右移一位。循环结束时恰好统计了从最高位 1 开始的所有二进制位。

关键点在于循环条件是 x > 0：一旦 x 变成 0，就说明已经到达最高位，更高位那些补位的 0 不会被统计进去。

判断与计数

对每个数调用一次统计过程，ones == zeros 时答案加一。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:22
 * update_at: 2026-08-17 22:40
 */
#include <bits/stdc++.h>
using namespace std;

// 判断正整数 x 的二进制表示中 1 和 0 的个数是否相等。
bool is_balanced(unsigned int x) {
    int ones = 0;   // 二进制中 1 的个数
    int zeros = 0;  // 二进制中 0 的个数
    while (x > 0) {
        if (x & 1U) {
            ones++;
        } else {
            zeros++;
        }
        x >>= 1;
    }
    return ones == zeros;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    int answer = 0;
    for (int i = 0; i < n; i++) {
        unsigned int value;
        cin >> value;
        if (is_balanced(value)) {
            answer++;
        }
    }
    cout << answer << '\n';
    return 0;
}

复杂度

设第 $i$ 个数的二进制位数为 $\lfloor \log_2 a_i \rfloor + 1$ 。

时间：每个数只扫描自己的二进制位，总时间复杂度为 $O\left(\sum_i \log a_i\right)$ 。
空间：只用常数个变量，空间复杂度为 $O(1)$ 。

总结

统计二进制位时从数值本身开始右移，就自然跳过了表示中的高位补零。这类逐位处理可以直接用位移和取最低位完成，不需要先把数转成字符串。

目录

形式化题目

思路

统计一个数的二进制位

判断与计数

代码

复杂度

总结