c++ - 按位比较

Question

#include <iostream>
using namespace std;

int main() {
    int n, a = 0xfffffff;
    cin >> n;
    while (n--) {
        string s;
        cin >> s;
        int c = 0;
        for (char ch : s)
            c |= 1 << (ch - 'a');
        a &= c;
    }
    cout << __builtin_popcount(a) << endl;
    return 0;
}

此代码用于查找某个字符是否在所有输入的字符串中至少出现一次。有人可以解释这段代码中发生了什么。我正在尝试学习 C++ 中的位运算，但我无法理解这里发生了什么。

Answer 1

代码不会确定特定字符是否存在于所有字符串中。

就是找出所有字符串中出现的字符个数。

这是代码的分解。

    int n, a = 0xfffffff;
    cin >> n;

n 是用户输入的参数，它决定了字符串的数量。假设 n 是 3

    while (n--) {
        string s;
        cin >> s;
        int c = 0;
        for (char ch : s)
            c |= 1 << (ch - 'a');
        a &= c;
    }

这是代码的主要部分..

你得到 n 个字符串，对于每个字符串，你将其组成的字符存储在一个位数组中

例如，假设第一个字符串是“stack”。你在这里遍历字符

    for (char ch : s)
        c |= 1 << (ch - 'a');

对于每个字符串，c 都被初始化为 0。

在这个“stack”的例子中，让我们看看 c 发生了什么

c = c | 1 << ('s'-'a') => c = c | 1 << 18 (18th bit of c is set to 1)

c = c | 1 << ('t'-'a') => c = c | 1 << 19 (19th bit of c is set to 1)

c = c | 1 << ('a'-'a') => c = c | 1 << 0 (0th bit of c is set to 1)

c = c | 1 << ('c'-'a') => c = c | 1 << 2 (2nd bit of c is set to 1)

c = c | 1 << ('k'-'a') => c = c | 1 << 10 (10th bit of c is set to 1)

note that 1 << n means that 1 is left shifted by n digits. so 1 << 3 is = 0001 << 3 = binary 1000 = 2^3 = 8 (In case you did not understand shifting)

现在c是一个整数，它的0、2、10、18、19位被设置为1。a在循环之前被初始化为全1。

a &= c; this gets rid of all 1's except 0,2,10,18 and 19.

我们对所有字符串继续这个。最后，a 将在所有字符串中占用的位置设置 1 位。

例如，如果字符串二是“aaaaa”

computing c reveals that c has only its 0th bit set.

a &= c; this gets rid of all 1's except 0 (ie., it sets 2,10,18 and 19th bits to 0, since they don't occur in "aaaaa")

字符串 3 是 "zzzzza"，最后只设置 a 的第 0 位

因此，所有这些字符串中出现的字符个数都是1