java - 解释使用位 vector 来确定是否所有字符都是唯一的

Question

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

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

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

此运算符 << 是一个左位移位器，它采用该数字或操作数的二进制表示并将其移动到由右侧的操作数或数字指定的许多位置，例如仅在二进制中的十进制数。我们乘以 2 为底——当我们向上移动时，很多地方不是以 10 为底——所以右边的数字是指数，左边的数字是 2 的底数倍数。

此运算符|=(称为按位或赋值)将左侧的操作数与右侧的操作数取或并将结果分配给左侧的操作数(x |= y 相当于x = x | y) .同样，运算符('&')将'和'左侧的运算符与右侧的运算符。这也有一个按位与赋值(x &= y 等价于 x = x & y)。

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

有 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

现在，它声明了一个重复