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

string java bit-manipulation bitvector

2022-08-31 06:31:27

我对位向量如何做到这一点感到困惑（不太熟悉位向量）。下面是给出的代码。有人可以带我完成这个吗？

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

我有一个偷偷摸摸的怀疑，你从我正在读的同一本书中得到了这个代码......这里的代码本身并不像运算符那样神秘 - |=，&，<<这些通常不被我们外行人使用 - 作者没有费心花费额外的时间来解释过程，也没有在这里涉及的实际机制是什么。一开始，我对这个主题上以前的答案感到满意，但只是在抽象的层面上。我回到它，因为我觉得需要一个更具体的解释 - 缺乏一个总是让我感到不安。

这个运算符<<是一个左按位移位器，它采用该数字或操作数的二进制表示形式，并将其移动到由操作数或右侧数字指定的许多位置，就像十进制数仅在二进制文件中一样。我们乘以2为基数 - 当我们向上移动时，许多地方不是以10为基数 - 所以右边的数字是指数，左边的数字是2的基数倍数。

此运算符 |=（称为按位 OR 赋值）获取左侧的操作数，或将其与右侧的操作数一起使用，并将结果分配给左侧操作数（x |= y 等效于 x = x | y）。类似地，运算符（'&'）将“和”运算符的左侧与右侧。这也有一个按位 AND 赋值（x &= y 等价于 x = x & y）。

因此，我们在这里有一个哈希表，每次检查器获得或'd（）时，它都存储在一个32位二进制数中，其字母的指定二进制值的相应位被设置为true。字符的值是和与检查器（）的d - 如果它大于0，我们知道我们有一个dupe - 因为两个相同的位设置为true并且一起将返回true或'1''。checker |= (1 << val)checker & (1 << val)) > 0

有26个二进制位置，每个位置对应于一个小写字母 - 作者确实说过假设字符串只包含小写字母 - 这是因为我们只剩下6个（32位整数）位置可供消费 - 并且我们得到的碰撞

00000000000000000000000000000001 a 2^0

00000000000000000000000000000010 b 2^1

00000000000000000000000000000100 c 2^2

00000000000000000000000000001000 d 2^3

00000000000000000000000000010000 e 2^4

00000000000000000000000000100000 f 2^5

00000000000000000000000001000000 g 2^6

00000000000000000000000010000000 h 2^7

00000000000000000000000100000000 i 2^8

00000000000000000000001000000000 j 2^9

00000000000000000000010000000000 k 2^10

00000000000000000000100000000000 l 2^11

00000000000000000001000000000000 m 2^12

00000000000000000010000000000000 n 2^13

00000000000000000100000000000000 o 2^14

00000000000000001000000000000000 p 2^15

00000000000000010000000000000000 q 2^16

00000000000000100000000000000000 r 2^17

00000000000001000000000000000000 s 2^18

00000000000010000000000000000000 t 2^19

00000000000100000000000000000000 u 2^20

00000000001000000000000000000000 v 2^21

00000000010000000000000000000000 w 2^22

00000000100000000000000000000000 x 2^23

00000001000000000000000000000000 y 2^24

00000010000000000000000000000000 z 2^25

因此，对于输入字符串“azya”，因为我们一步一步地移动

字符串“a”

a      =00000000000000000000000000000001
checker=00000000000000000000000000000000

checker='a' or checker;
// checker now becomes = 00000000000000000000000000000001
checker=00000000000000000000000000000001

a and checker=0 no dupes condition

字符串 'az'

checker=00000000000000000000000000000001
z      =00000010000000000000000000000000

z and checker=0 no dupes 

checker=z or checker;
// checker now becomes 00000010000000000000000000000001

字符串 “azy”

checker= 00000010000000000000000000000001    
y      = 00000001000000000000000000000000 

checker and y=0 no dupes condition 

checker= checker or y;
// checker now becomes = 00000011000000000000000000000001

字符串 'azya'

checker= 00000011000000000000000000000001
a      = 00000000000000000000000000000001

a and checker=1 we have a dupe

现在，它声明了一个副本

答案 2

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

大小。具有固定大小，通常为4个字节，这意味着8 * 4 = 32位（标志）。位向量通常可以具有不同的大小，或者您应该在构造函数中指定大小。int
原料药。使用位向量，您将更容易阅读代码，可能是这样的：

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

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

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

也可能更快一点，因为具有位的操作级别非常低，可以由CPU按原样执行。BitVector允许编写稍微少一点神秘的代码，而且它可以存储更多的标志。int

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