题意描述

给定一个数列 {ai}\{a_i\}{ai​}，求找到一组 $i,j(i\ne j)$，使 $a_i\mathrm{and}{a}_j$ 最大。

约定记号

设最优解的 $i=i_0$，$j=j_0$。

也就是当 $i=i_0,j=j_0$ 时，$a_i\mathrm{and}{a}_j$ 最大。

解题思路

设当前寻找最优解的范围是 $[l,r]$，也就是说目前可以确定 $l\le i_0,j_0\le r$。初始时 $l=1,r=n$。

先将所有数从小到大排序，从高到低检查每一位，分讨这一位上的情况，逐步缩小最优解所在范围。

1. 这位全部相同。
   答案显然与这一位无关，$l,r$ 不用改动。

2. 这位上有且仅有一个 $1$，位于数列末尾。
   则最优解的这位一定为 $0$，将末尾的数这一位改成 $0$ 并插入排序。

3. 当前位为 $1$ 的数多于 $1$ 个。
   则可以确定最优解这一位一定是 $1$。二分出首个这一位为 $1$ 的位置 $s$ 并令 $l\leftarrow s$。

最后，当 $[l,r]$ 范围缩小到两个数时，可以确定 $i_0=l,j_0=r$ 并求出最优解。

时间复杂度 $O(n\log n)$。

Code

#include <bits/stdc++.h>
using namespace std;
constexpr int N=1e6+5;
int a[N];
int main(){
    cin.tie(0)->sync_with_stdio(0);
	int n,L,R;
    cin>>n;
    L=0,R=n-1;
	for(int i=0;i<n;++i) cin>>a[i];
    sort(a,a+n);
    for(int bit=1<<30;bit;bit>>=1){
        if((a[L]&bit)||!(a[R]&bit)) continue;  // 这一位全部相同
        if((a[R]&bit)&&!(a[R-1]&bit)){  // 只有1个1
            int t=a[R]^=bit,i;
            for(i=R-1;i>=L&&a[i]>t;--i) a[i+1]=a[i];
            a[i+1]=t;
        }else{  // 1的个数多于1
            int l=L,r=R,mid;
            while(l<r){
                mid=l+r>>1;
                if(a[mid]&bit) r=mid;
                else l=mid+1;
            }
            L=l;
        }
        if(R-L<=1) break;
    }
    assert(L<R);
    cout<<(a[L]&a[R]);
	return 0;
}

Update 2025.6.15：修正错误的图片。
Update 2025.6.16：微调公式。
Update 2025.12.6：优化语言表达和代码格式。