求有多少个二进制位,在所有给定的整数中都为 1。
给定 n 个非负整数。把它们都转换为二进制后,请统计有多少个二进制位在所有整数中均为 1。
二进制位从右向左编号 0、1、2……;若某个整数没有第 k 位,则视为 0。
例如 13、7、15 的二进制分别是 1101、0111、1111,第 0 位和第 2 位都是 1,所以答案是 2。
按位与 AND数二进制中 1 的个数逐位判定位运算
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n;第二行 n 个非负整数 |
| 输出 | 所有整数公共为 1 的位数 |
| 数据范围 | 2 ≤ n ≤ 20000 |
| 数值范围 | 0 ≤ aᵢ ≤ 10⁹(最多 30 位) |
int 即可(10⁹ < 2³⁰)把三个数按位对齐写出来,逐列看是否"全是 1"。
| 位号 | 13 = 1101 | 7 = 0111 | 15 = 1111 | 全是 1? |
|---|---|---|---|---|
| 第 3 位 | 1 | 0 | 1 | ❌(7 是 0) |
| 第 2 位 | 1 | 1 | 1 | ✅ |
| 第 1 位 | 0 | 1 | 1 | ❌(13 是 0) |
| 第 0 位 | 1 | 1 | 1 | ✅ |
第 0 位:13、7、15 都是 1 ✅
第 1 位:13 是 0,不满足 ❌
第 2 位:全都是 1 ✅
第 3 位:7 是 0,不满足 ❌
✅ 满足的位有第 0 位和第 2 位,共 2 个
13 AND 7 = 1101 & 0111 = 0101
0101 AND 15 = 0101 & 1111 = 0101
结果 0101 中有 2 个 1
✅ 与逐位检查结果一致
| 输入 | 二进制 | AND 结果 | 答案 | 说明 |
|---|---|---|---|---|
| 1 1 | 1 / 1 | 1 | 1 | 两个相同的 1 |
| 7 7 7 | 111 反复 | 111 | 3 | 完全相同的数 |
| 5 0 | 101 / 0 | 0 | 0 | 只要有一个 0,答案必为 0 |
| 8 4 2 1 | 1000 / 0100 / 0010 / 0001 | 0 | 0 | 没有一位重合 |
| 6 7 | 110 / 111 | 110 | 2 | 公共的两位 |
把所有数依次按位与,最后统计结果中 1 的个数
x &= x − 1 数 1 的个数。对第 0 ~ 30 位,各自检查是否所有数该位都为 1
| 方案 | 运算量(n=20000) | 代码量 |
|---|---|---|
| 全局 AND | 约 2 × 10⁴ 次 | 约 8 行 |
| 逐位扫描 | 约 6 × 10⁵ 次 | 约 15 行 |
输入若干非负整数,程序会列出它们的二进制、逐步求 AND,并统计公共为 1 的位数。
点按钮开始 →
#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; }
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)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
3 | 2 | 题面样例 |
2 | 1 | 两个 1,公共位只有第 0 位 |
3 | 3 | 完全相同的数 |
2 | 0 | 含 0 时答案必为 0 |
4 | 0 | 没有任何一位重合 |
2 | 2 | 110 与 111 的公共位 |
只用 res 一个变量,不需要保存整个数组。
✅ 2 万次运算,瞬间完成;这题考的是认出不变量:"公共为 1"就是按位与。
// 位运算"归纳"三个常用操作 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 的题 |