我对位向量如何工作感到困惑(对位向量不太熟悉)。这是给出的代码。有人可以帮我完成这个吗?
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做什么?
checker
int checker在这里用作比特的存储。整数值中的每个位都可以视为一个标志,因此最终int是一个位数组(标志)。代码中的每个位都说明是否在字符串中找到了具有位索引的字符。出于同样的原因,您可以使用位向量而不是int. 它们之间有两个区别:
int checker
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。以下是针对不同语言/平台的此数据结构的一些链接: