G3027 [GESP202609 三级] 公共二进制位 题解

知识点：位运算、集合交集、二进制计数。

解题思路

从第一个数开始，逐个与后续数进行按位与，最后统计结果的1位数。

为什么正确

某一位在按位与后为1，当且仅当所有输入在该位都为1，正是公共二进制位。

易错点

要求所有数共有，不是至少两个数共有；使用与运算而非或或异或。

复杂度

时间O(nw)，空间O(1)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,x;
    cin>>n>>x;
    while(--n) {
        int y;
        cin>>y;
        x&=y;
    }
    cout<<__builtin_popcount((unsigned)x);
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用6个自行生成的测试点。