了解位向量在查找字符串中的唯一字符时的用法

Question

我有以下代码使用位向量在字符串中查找唯一字符。我们假设它是仅包含小写字母的ASCII字符集。

我很难理解下面的位向量的用法。即使在通过程序调试并遵循更改之后，变量也会在每个循环之后通过。

// assuming that the characters range from a-z
static boolean isUniqueBitVector(String str) {
    int checker = 0;

    for(int i = 0; i < str.length(); i++) {
        int val = str.charAt(i) - 'a';

        if((checker & (1 << val)) > 0) {
            return false;
        } else {
            checker |= (1 << val);
        }
    }
    return true;
}

将val（字符串中每个字符的int表示形式）左移1，然后用checker（初始化为0）对其进行AND'运算，然后在else块中对其进行OR'运算的目的是什么。

Answer 1

checker是一个32位整数，我们分配给它的最低26位来存储每个字母的标志a-z。我们可以使用位，因为一个字母只能是唯一的一次。

int val = str.charAt(i) - 'a';计算与当前字母相对应的位的索引。这就是输入仅包含输入的假设a-z。val它将是一个介于0到25之间的数字。

通常，(1 << val)是与所选字母相对应的位。<<是左移运算符。它用于将1移到val左侧，该位置只有一个位。因此，例如，1<<3将为8。实际上，左移等于乘以2的幂。

(checker & (1 << val))验证所选位是否打开。该&操作被称为按位和。它组合了两个数字，并将两个都打开的任何位设置为打开。请记住，1 << val只有一点点打开。结果checker将为非零的唯一方法是是否checker已打开相同的位。在那种情况下，我们返回false，因为已经重复了一个字母。

如果找到了一个新字母，我们需要打开中的正确位checker。这是做什么的checker |= (1 << val);。如果按位或运算符（）|在任一操作数中都打开，则将其打开。同样，1 << val只有一点点。因此，or的结果是复制checker并打开该位（无论它是否已打开）。

您在此处看到的所有操作都是非常常见的习惯用法。希望我的解释对您有所帮助，因为您几乎肯定会在任何简单的代码中看到非常相似的东西。