GESP 题解库 / 3 级题解 / [GESP202609 三级] 公共二进制位 · 第 26 / 28 题
GESP202609 三级 · B4577 · 入门

公共二进制位

求有多少个二进制位,在所有给定的整数中都为 1。

📊
n ≤ 20000
数据规模
🔢
aᵢ ≤ 10⁹
数值范围
⚡
O(n)
时间复杂度
🎯
全局按位与
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给定 n 个非负整数。把它们都转换为二进制后,请统计有多少个二进制位在所有整数中均为 1。

二进制位从右向左编号 0、1、2……;若某个整数没有第 k 位,则视为 0。

例如 13、7、15 的二进制分别是 1101、0111、1111,第 0 位和第 2 位都是 1,所以答案是 2。

💡
人话翻译:把所有的数叠在一起看,找出那些"每一位上都写着 1"的列。这恰好就是"全部按位与"的结果:AND 只有在所有数该位都是 1 时才为 1。

🔍 关键词提取

按位与 AND数二进制中 1 的个数逐位判定位运算

已知条件

项目说明
输入第一行 n;第二行 n 个非负整数
输出所有整数公共为 1 的位数
数据范围2 ≤ n ≤ 20000
数值范围0 ≤ aᵢ ≤ 10⁹(最多 30 位)

需要解决的问题

02
思维导图
整理解题思路的全貌
🔗 全部 AND 再数 1
📥 读入
n 个整数
可达 10⁹(约 30 位)
int 足够
n 可达 20000
🔗 两种思路
思路一:逐位检查所有数
思路二:全部按位与
两者等价
思路二更简洁
🔢 数 1 的个数
x &= x − 1 循环
或 __builtin_popcount
或逐位移位
最多 30 次
⚠️ 易错点
误以为要统计"任意数为1"
用 int 但 aᵢ 超范围(本题不会)
n = 2 的边界
含 0 时答案必为 0
03
样例手算推导
样例 13、7、15 逐位对照

🧮 样例逐位拆解

把三个数按位对齐写出来,逐列看是否"全是 1"。

位号13 = 11017 = 011115 = 1111全是 1?
第 3 位101❌(7 是 0)
第 2 位111✅
第 1 位011❌(13 是 0)
第 0 位111✅
1
逐位检查

第 0 位:13、7、15 都是 1 ✅

第 1 位:13 是 0,不满足 ❌

第 2 位:全都是 1 ✅

第 3 位:7 是 0,不满足 ❌

✅ 满足的位有第 0 位和第 2 位,共 2 个

2
用 AND 验证

13 AND 7 = 1101 & 0111 = 0101

0101 AND 15 = 0101 & 1111 = 0101

结果 0101 中有 2 个 1

✅ 与逐位检查结果一致

🔑
为什么"全部 AND"等价于"逐位检查"?AND 的规则是"两位都为 1 结果才是 1"。把所有数依次 AND 起来,某一位最终为 1 ⟺ 每一个数在该位都是 1。这正好就是题目要的条件。

🧮 几个边界情形

输入二进制AND 结果答案说明
1 11 / 111两个相同的 1
7 7 7111 反复1113完全相同的数
5 0101 / 000只要有一个 0,答案必为 0
8 4 2 11000 / 0100 / 0010 / 000100没有一位重合
6 7110 / 1111102公共的两位
💡
一个重要推论:只要序列里出现了 0,那么 AND 的结果必然是 0(0 的每一位都是 0),答案就是 0。可以据此提前返回。
04
解法对比
全局 AND vs 逐位扫描

⚔️ 解法对比

🟢 全局 AND 再数 1(推荐) 推荐

把所有数依次按位与,最后统计结果中 1 的个数

  • 时间 O(n)
  • 代码 8 行
  • 逻辑最贴切题意
  • 不需要关心位数上限
💡
实现要点:先把答案初始化为第一个数,然后依次与后面的数做 AND,最后用 x &= x − 1 数 1 的个数。

🟠 逐位扫描

对第 0 ~ 30 位,各自检查是否所有数该位都为 1

  • 时间 O(n × 30)
  • 代码略长
  • 需要知道位数上限
  • 结果等价
⚠️
也能过:n = 20000 时 20000 × 30 = 6 × 10⁵ 次运算,完全可行。但从表达力上看,AND 写法更直接。

📈 性能对比

方案运算量(n=20000)代码量
全局 AND约 2 × 10⁴ 次约 8 行
逐位扫描约 6 × 10⁵ 次约 15 行
05
算法流程图
依次 AND,最后数 1
开始读入 n读入第一个数 a₁,令 res = a₁i 从 2 到 n读入 aᵢ;res = res AND aᵢn 个数都读完了吗?统计 res 的二进制中 1 的个数并输出结束还有数 → 继续 AND
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔗 公共二进制位计算器

输入若干非负整数,程序会列出它们的二进制、逐步求 AND,并统计公共为 1 的位数。

结果会显示在这里

点按钮开始 →

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

💻 完整 C++ 代码

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

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

    int res;
    scanf("%d", &res);              // 先读第一个数作为初始值

    for (int i = 1; i < n; i++) {
        int x;
        scanf("%d", &x);
        res &= x;                   // 依次按位与,等价于"所有数都为 1 的位"
    }

    // 统计 res 中 1 的个数
    int cnt = 0;
    while (res > 0) {
        res &= (res - 1);           // 每次消掉最低位的 1
        cnt++;
    }

    printf("%d\n", cnt);
    return 0;
}
🔑
为什么 res 要用第一个数初始化,而不是 0?如果初始化成 0,那么 0 AND 任何数 = 0,结果永远是 0,答案就永远错了。AND 运算的"单位元"是全 1,不是 0,所以必须用第一个数(或全 1 的掩码)来初始化。

📖 关键几行怎么看

代码作用为什么这样写
scanf("%d", &res)读第一个数当初始值AND 不能用 0 初始化
res &= x累积按位与一步就表达"与所有数都成立"
res &= (res - 1)消掉最低位的 1循环次数等于 1 的个数
while (res > 0)数 1 的循环res 变成 0 就说明数完了
⚠️
两个坑:① 把 res 初始化为 0,导致答案永远是 0;② 理解成"有多少个位至少在一个数里是 1"(那应该用 OR,而题目要求的是所有数都为 1,所以用 AND)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

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

输入答案考察点
3
13 7 15
2题面样例
2
1 1
1两个 1,公共位只有第 0 位
3
7 7 7
3完全相同的数
2
5 0
0含 0 时答案必为 0
4
8 4 2 1
0没有任何一位重合
2
6 7
2110 与 111 的公共位
✅
自查清单:① res 用第一个数初始化了吗?② 用的是 AND 不是 OR 吗?③ 数 1 的循环写对了吗?

🚨 易错点清单

⚠️
res 初始化为 0:0 AND 任何数都是 0,答案永远为 0。必须用第一个数初始化。
⚠️
把 AND 写成 OR:题目要的是"所有数都为 1",对应 AND;OR 得到的是"至少一个数为 1",含义完全不同。
⚠️
位数上限假设过窄:aᵢ 可达 10⁹,需要考虑到第 29 位左右,不要只想到 8 位。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n)
空间复杂度
O(1)
n 最大
20000
位数
最多 30

时间怎么算的?

空间都用在哪?

只用 res 一个变量,不需要保存整个数组。

✅ 2 万次运算,瞬间完成;这题考的是认出不变量:"公共为 1"就是按位与。

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

🔗 常用技巧小抄

// 位运算"归纳"三个常用操作
int AND_all = a[0];   for (int i=1;i<n;i++) AND_all &= a[i];   // 所有位都为 1
int OR_all  = a[0];   for (int i=1;i<n;i++) OR_all  |= a[i];   // 至少一个为 1
int XOR_all = a[0];   for (int i=1;i<n;i++) XOR_all ^= a[i];   // 出现奇数次的位

// 数 1 的个数
int cnt1(int x){ int c=0; while(x){ x &= (x-1); c++; } return c; }

// 判断第 k 位是否为 1
bool bitK(int x, int k) { return (x >> k) & 1; }

// 注意:AND 的初始值不能用 0(0 会把一切抹平)
// 若必须初始化,用全 1 掩码:
int MASK = ~0;                  // 全 1

🌟 举一反三

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

能力点本题怎么用还能迁移到
按位与的归纳AND 所有数 = 公共为 1 的位公共子串位、权限交集、状态压缩
按位或的归纳OR 所有数 = 至少一个为 1 的位权限并集、字母出现标记
位计数技巧x &= x−1所有需要统计二进制 1 的题
🌟
思考题:如果把问题改成"有多少个位至少在一个数里是 1",代码要改哪一处?答案会变大还是变小?(提示:把 AND 改成 OR 即可,答案一定不会变小——因为"至少一个"的条件比"全部"更宽松。)