按位比较

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

这里没有太多内容，一点一点地分解它会揭示它的作用：

#include <iostream>

using namespace std;

int main() {
  // Initialize a bitmask, here assumed to be 32-bits
  // which is probably "enough" for this case.
  int n, a = 0xfffffff;

  // Read in the number of strings to process
  cin >> n;

  // Assume n > 0
  while (n--) {
    string s;

    // Read in a string
    cin >> s;

    int c = 0;

    // For each character in this string
    for (char ch : s)
       // Turn on a bit on representing the character, where
       // 'a' is bit 0, 'b' is 1, etc.
       c |= 1 << (ch - 'a');

    // Apply this mask to a
    a &= c;
  }

  // Report on which bits are toggled
  cout << __builtin_popcount(a) << endl;

  return 0;
}

总的来说，这是一些非常草率的代码。任何非小写字母都可能导致未定义的行为。对于现代机器，大多数编译器都是 64 位的，因此仅设置 32 位可能不够。

请注意，当我在这里使用 "assume" 这个词时，我的意思是 可能会发生坏事 。

Answer 2

我们先来看看

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

您使用变量 c:

按位表示输入字符串的字符

如果字符a出现在字符串中，变量c中的位0设置为1，
如果字符b出现在字符串中，变量c中的第1位设置为1，
如果字符c出现在字符串中，变量c中的第2位设置为1，
等等。

c 中的所有其他位均为零。

完成一串后，代码

a &= c;

被处决。此代码将变量 a 中的位设置为 1，前提是它之前为 1，并且 c 中的相应位也为 1。然后函数继续读取下一个字符串并再次执行相同的操作。

在执行结束时，恰好 a 中所有 c 中的那些位被设置为 1 while 块。

Answer 3

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

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

这是代码的分解。

    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。

在这个“堆栈”示例中，让我们看看 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

按位比较

Bitwise comparisions

c++

bit-manipulation

bitwise-operators