企业官网建设流程全解析

第三题：按位与——数字宝藏大冒险

这道题是 CSP-J/S 2026 第二轮入门组的第三题。它和前两题很不一样：前面两题主要考察字符串和模拟判断，而这一题开始考查一个非常重要的知识点——二进制与位运算。

别担心！我们把它想象成一场寻宝游戏。每个数字都是一把藏着宝石的钥匙，我们要从中选出恰好 m 把，让它们共同拥有的宝石价值最大。

学完这道题，孩子们不仅能掌握按位与，还能理解一种非常经典的算法思想：从高位到低位，逐位尝试，能保留就保留。

一、先读懂题目：我们要做什么？

题目给出：

• n 个非负整数；

• 一个正整数 m ；

• 要从这 n 个数中，恰好选出 m 个；

• 对选出的这 m 个数进行二进制按位与；

• 让最后的结果尽可能大。

例如，样例 1：

4 2 3 15 12 12

意思是：

• 一共有 4 个数字：3、15、12、12；

• 要从中选出恰好 2 个；

• 让这两个数按位与的结果最大。

题目答案是：

12

我们先不急着写程序，先弄明白什么叫按位与。

二、按位与是什么？——两把钥匙共同拥有的宝石

在计算机中，每个整数都可以写成二进制。

例如：

十进制： 3 15 12 二进制： 0011 1111 1100

按位与使用符号&。

它的规则非常简单：

两个对应位置都是 1，结果才是 1；只要有一个是 0，结果就是 0。

我们来看一个例子：

0011 （3） & 1111 （15） ------------ 0011 （3）

再看：

1111 （15） & 1100 （12） ------------ 1100 （12）

所以：

3 & 15 = 3 15 & 12 = 12

可以把它想象成：

• 数字中的每一个1，代表拥有一颗宝石；

• 数字中的0，代表没有这颗宝石；

• 两把钥匙进行按位与，只有两把钥匙都拥有的宝石才能留下。

三、先用枚举法理解题目

我们先看样例 1：

4 2 3 15 12 12

一共有 4 个数，要选 2 个。

所有可能的选择有：

最大值是：

12

这样我们就理解题目了。

但是，孩子们要注意：枚举法虽然容易理解，却不能通过所有测试数据。

题目中：

1 ≤ m ≤ n ≤ 2 × 10^5

最多有 20 万个数。如果要从中挑选很多个数，逐一枚举所有组合，可能性会非常多，程序会运行得很慢。

有没有更聪明的方法呢？

有！这就是本题最重要的算法思想。

四、核心算法：从最高位开始，一位一位争取！

我们先想一个问题：

假设最后的答案是一个二进制数：

??????????

每个位置都可以是0或1。

我们希望这个数尽可能大，应该优先争取哪一位？

当然是最左边的高位！

例如：

1000 = 8 0111 = 7

虽然0111有三个 1，1000只有一个 1，但1000更大。

所以，判断一个二进制数的大小，要从高位开始比较。

本题的数字都小于 2^30，所以我们只需要考虑第 29 位到第 0 位，一共 30 位。

1. 假设：我们已经争取到了这些位

我们用一个变量ans保存目前已经确定的答案。

开始时：

int ans = 0;

它表示目前还没有争取到任何一颗宝石。

2. 从高位向低位尝试

先尝试第 29 位：

int temp = ans | (1 << 29);

这里有两个新知识：

• 1 << 29：把数字 1 向左移动 29 位，相当于得到只有第 29 位是 1 的数字；

• |：按位或，只要对应位置有一个 1，结果就是 1。

我们用temp表示：

假如最终答案的第 29 位也变成 1，会得到什么候选答案？

接下来，检查能不能选出至少 m 个数字，使得它们都包含temp中要求的所有 1。

3. 怎么判断一个数字是否包含这些 1？

假设：

temp = 1100

一个数字只有在temp为 1 的位置上也都是 1，才符合要求。

我们可以这样判断：

(a[i] & temp) == temp

为什么？

例如：

a[i] = 1111 temp = 1100 a[i] & temp = 1100

结果等于temp，说明这个数字包含了我们要求的所有 1。

再看：

a[i] = 1011 temp = 1100 a[i] & temp = 1000

结果不等于temp，说明它缺少一颗我们要求的宝石，不符合条件。

4. 数一数：符合要求的数字够不够？

我们遍历全部数字，统计有多少个数字满足：

(a[i] & temp) == temp

如果这样的数字数量不少于m，说明我们能够从中选出恰好m个数字，让它们的按位与结果至少包含temp中所有的 1。

于是，这一位就可以保留！

if (cnt >= m) { ans = temp; }

如果数量不足，就不能保留这一位，继续尝试下一位。

寻宝过程：高位优先

1. 尝试最高位

   如果有足够多的数字支持，就把这一位设为 1。

2. 尝试下一位

   保留已经成功的高位，再试着把新的一位也设为 1。

3. 继续向低位尝试

   能保留就保留，不能保留就放弃。

4. 所有位都检查完

   得到的ans就是最大的按位与结果。

五、为什么这样贪心一定正确？

这是孩子们需要真正理解的地方。

我们不是随便挑选数字，而是按照二进制的大小，从高位到低位做决定。

例如，假设当前已经确定了高位，接下来要判断某一位能不能变成 1。

• 如果能找到至少 m 个数字，它们都拥有目前要求的这些 1，那么就可以选出其中 m 个，保留这一位。

• 如果连 m 个都找不到，说明无论怎么选，都不可能让这一位成为 1，同时还保留前面已经确定的高位。

为什么不能为了低位而放弃高位？

因为高位的价值一定大于它右边所有低位的价值之和。例如：

1000（2） = 8 > 0111（2）=7

所以我们必须优先保证高位尽可能大，再考虑低位。

这就是本题的贪心思想：

从高位到低位，逐位尝试；能让答案变大的这一位，就尽量保留。

六、完整 C++ 程序

现在把刚才的寻宝过程写成程序。

#include <iostream> #include <vector> using namespace std; int main() { int n, m; cin >> n >> m; vector<int> a(n); // 读入 n 个数字 for (int i = 0; i < n; i++) { cin >> a[i]; } // 保存目前找到的最大答案 int ans = 0; // 从第 29 位开始，一直尝试到第 0 位 for (int bit = 29; bit >= 0; bit--) { // 假设当前这一位也可以变成 1 int temp = ans | (1 << bit); // 统计有多少个数字包含 temp 中要求的所有 1 int cnt = 0; for (int i = 0; i < n; i++) { if ((a[i] & temp) == temp) { cnt++; } } // 如果符合要求的数字不少于 m 个，就保留这一位 if (cnt >= m) { ans = temp; } } cout << ans << endl; return 0; }

七、拿样例 2，完整走一遍算法

输入：

5 3 31 3 1 15 7

我们有 5 个数字，要选 3 个。

题目答案是 7。

先把这几个数字写成二进制：

我们从高位开始尝试。

第一次：尝试第 4 位

第 4 位对应的数值是 16。

要让答案包含这一位，需要有至少 3 个数字的第 4 位都是 1。

但是只有 31 满足，只有 1 个数字。

符合要求的数字：31 数量：1 需要：3

数量不够，所以放弃第 4 位。

第二次：尝试第 3 位

第 3 位对应的数值是 8。

符合要求的数字有：

31、15

只有 2 个，不够 3 个。

所以第 3 位也不能保留。

第三次：尝试第 2 位

第 2 位对应的数值是 4。

符合要求的数字有：

31、15、7

刚好有 3 个！

所以我们可以保留这一位：

ans = 00100

第四次：尝试第 1 位

现在我们已经有了00100，接下来尝试把第 1 位也变成 1：

temp = 00110

检查哪些数字包含00110：

31：11111 符合 15：01111 符合 7 ：00111 符合

还是有 3 个！

所以保留这一位：

ans = 00110

第五次：尝试第 0 位

继续尝试：

temp = 00111

检查：

31：11111 符合 15：01111 符合 7 ：00111 符合

依然有 3 个！

所以第 0 位也保留。

最终：

ans = 00111

换成十进制：

00111（2）=7

输出：

7

八、复杂度分析：为什么这个算法跑得快？

我们一共检查 30 个二进制位。

每检查一位，都要遍历一次全部 n 个数字。

所以总的时间复杂度是：

O(30n) = O(n)

空间复杂度：

O(n)

因为我们只需要一个数组保存输入数字。

题目最多有 20 万个数字，因此大约只需要进行：

30 * 200000 = 6000000次判断，完全可以接受。

九、学生有可能犯的几个错误

错误 1：从低位开始尝试。

不行！我们要最大化数字，必须优先考虑高位。高位的价值远远大于后面所有低位的总和。

错误 2：只判断有没有一个数字符合条件。

不行！题目要求选出恰好 m 个数字，因此必须统计符合条件的数量，判断：

cnt >= m

错误 3：把按位与写成逻辑与。

a[i] & temp

是按位与，比较的是二进制的每一位。

a[i] && temp

是逻辑与，判断的是两个表达式是否都为真。

它们完全不是一回事！

错误 4：忘记保留已经成功的高位。

每次尝试都要写：

int temp = ans | (1 << bit);

不能只写1 << bit，否则之前已经争取成功的高位就丢失了。

十、举一反三：遇到类似题目怎么办？

这道题真正值得学生掌握的是一种通用算法思想：

答案可以用二进制表示，而且我们希望答案尽可能大时，可以考虑从高位到低位逐位贪心。

以后遇到类似问题，可以先问自己：

1. 答案是不是一个整数？

2. 能不能把答案拆成二进制的每一位？

3. 高位是不是比低位更重要？

4. 能不能判断“如果这一位设为 1，是否还存在满足要求的方案”？

如果这几个问题的答案都是肯定的，就可以考虑这种逐位贪心的方法。

当然，并不是所有最大值问题都适合这样做，还需要能够正确判断每次尝试是否可行。