题解

题目解析

• 输入输出：第一行输入整数 $n$ 表示数据量，第二行输入 $n$ 个非负整数。输出两个整数：所有数字二进制表示中 $1$ 的总个数，以及校验码（$1$ 的个数为奇数输出 $1$，否则输出 $0$）。
• 数据范围：$1 \le n \le 100$，$0 \le c_i \le 255$（即每个数可用 $8$ 位二进制表示）。
• 复杂度要求：由于每个数最多 $8$ 位二进制，时间复杂度 $O(n \cdot \log(\max(c_i))) \approx O(n)$，即 $O(100)$ 级别；空间复杂度 $O(1)$。
• 算法知识点：二进制位运算、奇偶校验、逐位统计

思路解析

1. 统计所有数字的1的个数：遍历每个输入数字，对每个数字通过不断除以 $2$（右移）的方式，逐位检查其二进制表示中 $1$ 的个数。
2. 逐位检查原理：对于任意整数 $x$，$x \bmod 2$ 的结果即为 $x$ 二进制表示的最低位（$0$ 或 $1$）。若为 $1$ 则计数器加一，随后将 $x$ 除以 $2$（整数除法等价于右移一位），继续检查下一位，直到 $x$ 变为 $0$。
3. 计算校验码：累计得到所有数字中 $1$ 的总数 $\textit{one\_cnt}$ 后，校验码即为 $\textit{one\_cnt} \bmod 2$（奇数为 $1$，偶数为 $0$）。
4. 输出结果：按格式要求依次输出 $1$ 的总数和校验码。

完整代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int one_cnt = 0;  // 统计所有数字二进制中1的总数
    while (n--) {
        int x;
        cin >> x;
        // 逐位提取二进制表示，统计1的个数
        while (x != 0) {
            if (x % 2 == 1) {  // 关键：检查最低位是否为1（等价于 x & 1）
                one_cnt++;
            }
            x /= 2;  // 关键：右移一位（等价于 x >>= 1），处理下一位
        }
    }
    // 输出1的总数，以及奇偶校验码（奇数为1，偶数为0）
    cout << one_cnt << " " << one_cnt % 2 << endl;
    return 0;
}