GESP 题解库 / 3 级题解 / [GESP202506 三级] 奇偶校验 · 第 7 / 28 题
GESP202506 三级 · B4358 · 简单

奇偶校验

统计所有数二进制中 1 的总个数,并据此给出校验码:总数为奇数则校验码 1,否则 0。

📊
n ≤ 100
数据规模
🔢
cᵢ ≤ 255
数值范围
⚡
O(n log C)
时间复杂度
🎯
统计二进制 1 的个数
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给定 n 个非负整数 c₁, c₂, …, cₙ。它们的校验码取决于这些整数在二进制下 1 的数量之和的奇偶性:

输出两个整数:1 的总个数、校验码。

💡
人话翻译:把每个数都写成二进制,数一数一共有多少个 1,记这个总和为 S。然后看 S 是奇数还是偶数:奇数输出 1,偶数输出 0。这题是"数位统计"的入门题。

🔍 关键词提取

二进制popcount奇偶判断位运算

已知条件

项目说明
输入第一行 n;第二行 n 个非负整数
输出两个整数:1 的总个数、校验码
数据范围1 ≤ n ≤ 100
数值范围0 ≤ cᵢ ≤ 255(即最多 8 位二进制)

需要解决的问题

02
思维导图
整理解题思路的全貌
🔢 数 1 的个数再判奇偶
📥 读入
n 和 n 个数
总和 total = 0
每个数最多 8 位
循环累加
🔍 数 1 的方法
逐位:x & 1 后右移
快速:x &= x − 1
库函数:popcount
三种都对
✅ 判奇偶
total 是奇数 → 输出 1
total 是偶数 → 输出 0
等价于 total & 1
total % 2 也行
⚠️ 注意点
0 不做特殊处理
输出两个数用空格分隔
先输出总数再输出校验码
顺序别写反
03
样例手算推导
样例 1 逐个拆二进制

🧮 样例 1:71 69 83 80,答案 13 1

把每个数拆成二进制,数一数各有几个 1。

1
71 的二进制

71 = 64 + 4 + 2 + 1 = 1000111₂

数一数:1 0 0 0 1 1 1 → 有 4 个 1

贡献 4

2
69 的二进制

69 = 64 + 4 + 1 = 1000101₂

1 0 0 0 1 0 1 → 有 3 个 1

贡献 3

3
83 的二进制

83 = 64 + 16 + 2 + 1 = 1010011₂

1 0 1 0 0 1 1 → 有 4 个 1

贡献 4

4
80 的二进制

80 = 64 + 16 = 1010000₂

1 0 1 0 0 0 0 → 有 2 个 1

贡献 2

5
汇总判断

总数 = 4 + 3 + 4 + 2 = 13

13 是奇数

✅ 校验码 = 1,输出 "13 1"

📊 逐个统计

数值二进制1 的个数累计
71100011144
69100010137
831010011411
801010000213
🔑
13 是奇数 → 校验码 1。如果总和是偶数,校验码就是 0,这就是"偶校验"的含义:让 1 的总个数保持偶数。

🧮 样例 2:1 2 4 8 16 32,答案 6 0

这组数据都是 2 的幂,每个数的二进制里恰好只有一个 1。

数值二进制1 的个数
111
2101
41001
810001
16100001
321000001
💡
观察:2 的幂(1, 2, 4, 8, 16, …)在二进制里必定只有 1 个 1,这是个很实用的性质。6 个数 → 总数 6 → 偶数 → 校验码 0。
04
解法对比
三种数 1 的写法

⚔️ 解法对比

🟢 x &= x − 1 技巧(推荐) 推荐

每次消掉最低位的 1,循环次数 = 1 的个数

  • 循环次数等于 1 的个数
  • 本题最多 8 次
  • 不需要移位运算
  • 代码短
💡
原理:x − 1 会把最低位的那个 1 变成 0、并把它右边的 0 全部变成 1,两者相与就恰好消掉最低位的 1。

🔵 __builtin_popcount

GCC 内置函数,直接返回 1 的个数

  • 一行搞定,最快
  • 但属于编译器扩展
  • 有些评测环境不支持
  • 考试时慎用
⚠️
提示:GESP/NOI 通常用 GCC,可以放心用;但为了保险,建议同时会写手写版本。

📈 性能对比

写法本题运算量可移植性
x &= x − 1最多 800 次⭐⭐⭐⭐⭐
逐位移位最多 800 次⭐⭐⭐⭐⭐
popcount100 次⭐⭐⭐(依赖编译器)
05
算法流程图
外层 n 个数、内层数 1
开始读入 n;total = 0读入下一个数 xx 还有 1 吗?(x > 0)x = x & (x − 1),total 加 1n 个数都处理完了吗?是 ✓下一步否 ✗继续读下一个数校验码 = total 除以 2 的余数输出 total 和校验码结束还有数没统计 → 继续
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔢 二进制 1 计数与校验码

输入若干个 0 ~ 255 的整数,程序会给出每个数的二进制、1 的个数,以及总校验码。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

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

int main() {
    int n;
    scanf("%d", &n);

    int total = 0;
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        // 数二进制中 1 的个数:每次消掉最低位的 1
        while (x > 0) {
            x &= (x - 1);
            total++;
        }
    }

    int check = total % 2;          // 奇数 -> 1,偶数 -> 0
    printf("%d %d\n", total, check);
    return 0;
}
🔑
为什么 x &= x - 1 能数出 1 的个数?
举例 x = 12 = 1100₂:
x − 1 = 1011₂,相与得 1000₂(消掉了最低位的 1)
x − 1 = 0111₂,相与得 0000₂(又消掉一个 1)
共执行 2 次 → 12 里有 2 个 1。循环次数正好等于 1 的个数。

📖 三种写法对照

写法代码特点
逐位移位while (x) { c += x & 1; x >>= 1; }最直观,固定循环位数次
消位技巧while (x) { x &= x - 1; c++; }循环次数 = 1 的个数,效率更高
库函数c = __builtin_popcount(x);一行完成,但依赖 GCC 扩展
⚠️
注意输出顺序:题目要求先输出"1 的总数量",再输出"校验码"。写成 printf("%d %d", check, total) 就反了。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
1
0
0 00 里没有 1,总数 0 是偶数
1
1
1 1单个 1,奇数
1
255
8 0255 = 11111111₂,8 个 1
4
71 69 83 80
13 1题面样例 1
6
1 2 4 8 16 32
6 0题面样例 2,都是 2 的幂
✅
自查清单:① 0 会不会被少数或多数?② 输出顺序对不对?③ 用 total % 2 求校验码了吗?

🚨 易错点清单

⚠️
把 0 当成特殊情况:0 的二进制没有 1,用 while (x > 0) 自动跳过,不需要特判;如果用 do-while 就会多加一次。
⚠️
输出顺序写反:先总数、后校验码。
⚠️
校验码判断写错:"总数为奇数 → 1",即 total % 2,不要写成 (total + 1) % 2。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n × 位数)
空间复杂度
O(1)
n 最大
100
每数位数
最多 8

时间怎么算的?

空间都用在哪?

只需要 total 和循环变量两个整数。

✅ 最坏不到 1000 次操作,任何写法都远远够快。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 数 1 的三种写法
int countOnes1(int x) { int c=0; while(x){ c += x & 1; x >>= 1; } return c; }
int countOnes2(int x) { int c=0; while(x){ x &= (x-1); c++; } return c; }
int countOnes3(int x) { return __builtin_popcount(x); }

// 判断奇偶的三种写法(等价)
bool odd1 = (total % 2 == 1);
bool odd2 = (total & 1);
bool odd3 = (total % 2 != 0);

// 相关位运算技巧
// x & -x      取最低位的 1
// x | (x-1)   把最低位起的 0 全变 1
// x ^ (x-1)   取最低位 1 及其右边的所有位

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
二进制表示把十进制拆成 0/1 序列进制转换、位运算、状态压缩
x &= x − 1 技巧快速数 1 的个数位计数、判断是否为 2 的幂
奇偶判断总数取模 2校验码、奇偶分类、布隆过滤思想
🌟
思考题:奇偶校验只能检测出"奇数个位出错",如果传输中同时错了 2 位,校验码就发现不了。有没有更强的校验方式?(提示:查 CRC 校验、汉明码,汉明码能定位并纠正 1 位错误。)