解释使用位向量来确定是否所有字符都是唯一的

 

问题描述：

我对位向量如何工作感到困惑（对位向量不太熟悉）。这是给出的代码。有人可以帮我完成这个吗？

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做什么？

 

第 1 个答案：

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

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

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

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。以下是针对不同语言/平台的此数据结构的一些链接：


这个问题在这里已经有了答案 ：11年前关闭。可能重复：是否有 JavaScript函数可以填充字符串以达到确定的长度？如何在不使用任何 3rd 方库的情况下将 JavaScri ...