说明使用位向量确定所有字符是否唯一

Question

我对位向量如何实现此功能感到困惑（对位向量不太熟悉）。这是给出的代码。有人可以引导我完成这个吗？

public static boolean isUniqueChars(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;
        checker |= (1 << val);
    }
    return true;
}

特别是，这是checker怎么做的？

Answer 1

int checker在这里用作位存储。整数值中的每个位都可以视为一个标志，因此最终int是一个位数组（标志）。代码中的每一位都说明是否在字符串中找到带有位索引的字符。您可以出于相同的原因而不是使用位向量int。它们之间有两个区别：

• 大小 。int具有固定大小，通常为4个字节，这意味着8 * 4 = 32位（标志）。位向量通常可以具有不同的大小，或者应在构造函数中指定大小。

• API 。使用位向量，您将更容易阅读代码，可能是这样的：

vector.SetFlag(4, true); // set flag at index 4 as true

因为int您将具有较低级别的位逻辑代码：

checker |= (1 << 5); // set flag at index 5 to true

也可能int会快一点，因为带位的操作级别很低，可以按原样由CPU执行。BitVector允许编写更少的加密代码，而它可以存储更多的标志。

供将来参考：位向量也称为bitSet或bitArray。这是针对不同语言/平台的此数据结构的一些链接：

• CPP：位集
• Java：BitSet
• C＃：BitVector32和BitArray