小编典典

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

all

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

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


阅读 70

收藏
2022-07-28

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

2022-07-28