统计所有数二进制中 1 的总个数,并据此给出校验码:总数为奇数则校验码 1,否则 0。
给定 n 个非负整数 c₁, c₂, …, cₙ。它们的校验码取决于这些整数在二进制下 1 的数量之和的奇偶性:
输出两个整数:1 的总个数、校验码。
二进制popcount奇偶判断位运算
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n;第二行 n 个非负整数 |
| 输出 | 两个整数:1 的总个数、校验码 |
| 数据范围 | 1 ≤ n ≤ 100 |
| 数值范围 | 0 ≤ cᵢ ≤ 255(即最多 8 位二进制) |
x &= x - 1 技巧、库函数 __builtin_popcountS & 1把每个数拆成二进制,数一数各有几个 1。
71 = 64 + 4 + 2 + 1 = 1000111₂
数一数:1 0 0 0 1 1 1 → 有 4 个 1
贡献 4
69 = 64 + 4 + 1 = 1000101₂
1 0 0 0 1 0 1 → 有 3 个 1
贡献 3
83 = 64 + 16 + 2 + 1 = 1010011₂
1 0 1 0 0 1 1 → 有 4 个 1
贡献 4
80 = 64 + 16 = 1010000₂
1 0 1 0 0 0 0 → 有 2 个 1
贡献 2
总数 = 4 + 3 + 4 + 2 = 13
13 是奇数
✅ 校验码 = 1,输出 "13 1"
| 数值 | 二进制 | 1 的个数 | 累计 |
|---|---|---|---|
| 71 | 1000111 | 4 | 4 |
| 69 | 1000101 | 3 | 7 |
| 83 | 1010011 | 4 | 11 |
| 80 | 1010000 | 2 | 13 |
这组数据都是 2 的幂,每个数的二进制里恰好只有一个 1。
| 数值 | 二进制 | 1 的个数 |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 10 | 1 |
| 4 | 100 | 1 |
| 8 | 1000 | 1 |
| 16 | 10000 | 1 |
| 32 | 100000 | 1 |
每次消掉最低位的 1,循环次数 = 1 的个数
x − 1 会把最低位的那个 1 变成 0、并把它右边的 0 全部变成 1,两者相与就恰好消掉最低位的 1。GCC 内置函数,直接返回 1 的个数
| 写法 | 本题运算量 | 可移植性 |
|---|---|---|
| x &= x − 1 | 最多 800 次 | ⭐⭐⭐⭐⭐ |
| 逐位移位 | 最多 800 次 | ⭐⭐⭐⭐⭐ |
| popcount | 100 次 | ⭐⭐⭐(依赖编译器) |
输入若干个 0 ~ 255 的整数,程序会给出每个数的二进制、1 的个数,以及总校验码。
点按钮开始 →
#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 的个数?| 写法 | 代码 | 特点 |
|---|---|---|
| 逐位移位 | while (x) { c += x & 1; x >>= 1; } | 最直观,固定循环位数次 |
| 消位技巧 | while (x) { x &= x - 1; c++; } | 循环次数 = 1 的个数,效率更高 |
| 库函数 | c = __builtin_popcount(x); | 一行完成,但依赖 GCC 扩展 |
printf("%d %d", check, total) 就反了。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
1 | 0 0 | 0 里没有 1,总数 0 是偶数 |
1 | 1 1 | 单个 1,奇数 |
1 | 8 0 | 255 = 11111111₂,8 个 1 |
4 | 13 1 | 题面样例 1 |
6 | 6 0 | 题面样例 2,都是 2 的幂 |
total % 2 求校验码了吗?while (x > 0) 自动跳过,不需要特判;如果用 do-while 就会多加一次。total % 2,不要写成 (total + 1) % 2。x &= x − 1 或移位,最多循环"二进制位数"次(本题 ≤ 8)只需要 total 和循环变量两个整数。
✅ 最坏不到 1000 次操作,任何写法都远远够快。
// 数 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 | 校验码、奇偶分类、布隆过滤思想 |