位运算比较

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++中的位运算，但我无法理解这里发生了什么。

- srip

---

你从哪里得到这段代码的？你应该给出作者署名，如果可能的话，询问作者的意图。 - 463035818_is_not_a_number

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'）=＆gt; c = c | 1 << 18（c的第18位设置为1）

c = c | 1 <<（'t' - 'a'）=＆gt; c = c | 1 << 19（c的第19位设置为1）

c = c | 1 <<（'a' - 'a'）=＆gt; c = c | 1 << 0（c的0位设置为1）

c = c | 1 <<（'c' - 'a'）=＆gt; c = c | 1 << 2（c的第2位设置为1）

c = c | 1 <<（'k' - 'a'）=＆gt; c = c | 1 << 10（c的第10位设置为1）

请注意，1 << n表示1向左移动n位数字。所以1 << 3 = 0001 << 3 =二进制1000 = 2 ^ 3 = 8（如果您不理解移位，请参阅说明）

现在，c是一个整数，其0,2,10,18,19位设置为1。循环之前，a被初始化为所有1。

a＆= c; 这会除去除0,2,10,18和19之外的所有1。

我们为所有字符串继续此操作。最后，a将在所有字符串中占用的位置上设置1位。

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

计算c会发现c只有它的0位设置。

a＆= c; 这将除去除第0位外的所有1（即，它将第2、10、18和19位设置为0，因为它们不出现在“aaaaa”中）

而字符串3是“zzzzza”，最后，a的仅有的0位将被设置

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

- TransientObject

Answer 2

这里没有太多的内容，逐步分解可以揭示它的功能：

#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位可能不足够。

请注意，当我在这里使用“假设”一词时，我的意思是 坏事情可能会发生。

- tadman

---

奇怪的是，a初始化中只有7个f，而不是8个。这意味着掩码只有28位被设置。我猜代码作者只需要28位，因为字母表中只有26个字母？ - KABoissonneault

@KABoissonneault 这是一个很好的观察。整个代码块都需要进行重构。我不确定为什么它不从零开始，而是从任意数量的1开始。 - tadman

好的，英文字母有26个，所以28个足够了。 - coyotte508

@KABoissonneault 不，但如果所有字符串中都存在 '{' 或 '|'，那么结果将超出预期，这确实是一种行为错误。 - coyotte508

@KABoissonneault：使用a &= c;可以消除a的初始值中的任何额外的1。 - Nick Matteo

Answer 3

让我们先看一下。

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且相应的c位也为1，则将一个位设置为1。然后函数继续读取下一个字符串并重复执行。

在执行结束时，只有在while块中所有c的1位才被设置为1的a位被设置为1。

- Xaver