解题思路

核心思想：按位贪心筛选。从高位到低位（第 30 位到第 0 位，因为输入不超过 $2\times10^9<2^{31}$ ），尝试把当前位设为 1，检查是否至少有两个数能同时满足“这些位均为 1”。若能满足，就保留这些候选数并把该位并入答案；否则跳过该位。
相关算法：逐位贪心 + 过滤候选集合。每次尝试的新掩码 mask = ans | (1<<b)，统计满足 (x & mask) == mask 的元素个数（并在成功时把候选集合更新为这部分元素）。
正确性说明：最大按位与的每一位独立决定。若某一位能与出 1，则必存在至少两个数同时具备这位为 1 且保留之前已确定的高位为 1；因此自高到低逐步确定为 1 的位不会影响已确定位的可行性。

复杂度分析

时间复杂度：每一位最多遍历一遍候选集合，共 31 位，复杂度为 $O(31n)\approx O(n)$ 。

P4229.第1题-按位与

1000ms

Tried: 31

Accepted: 12

Difficulty: 3

所属公司 : 滴滴

算法与标签>贪心算法

题目内容

C/C++中的按位与运算符“&”是双目运算符，其功能是参与运算的两数各对应的二进制位相与，只有对应的两个二进制位都为 $1$ 时，结果位才为 $1$ 。参与运算的两个数均以补码出现。例如的计算如下（右下数字 $2$ 表示 $2$ 进制）： $00000011_{2}$ & $00001010_{2}$ 现在，给你 $n$ 个数字，请你从中挑选 $2$ 个数字，使他们的按位与运算结果在所有可能的挑选方式中是最大的。

输入描述

第一行包含一个正整数 $n（2≤n≤300000）$ ，表示给定数字的数量。接下来 $n$ 行，每行包含 $1$ 个整数 $a$ （0≤a≤2000000000）$，表示一个给定的数字。

输出描述

输出仅一行，包含一个数字，表示题目所求的最大按位与的结果。

样例1

输入

输出

说明

$8$ & $10=8$ ， $8$ & $2=0$ ， $10$ & $2=2$ ，所以最大的一个结果是 $8$ 。

输入

预期输出（选填）

解题思路

复杂度分析

P4229.第1题-按位与

题目内容

输入描述

输出描述

样例1

Status

Development

Support

About