java - Java 新手 - 试图理解 : checker |= (1 << val)

Question

以下代码将检查字符串中是否有重复字符，但我不理解 if 子句:

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 << val) 是如何工作的吗？还有那个“如果”语句。

Answer 1

我也在看这本书 Cracking the Code Interview并最终在谷歌上搜索了一个明确的解释。我终于明白了这个概念。

这是方法。

注意:

1. 我们假设，在下面的代码中，字符串只是小写的“a”到“z”。这将允许我们只使用一个 int。

2. Java 整数的大小为 32

3. 小写字母的数量是 26

So we can clearly set 0/1 (true or false) value inside one integer in decimal notation.

1. 它类似于bool visited[32] 。 bool 使用 1 个字节。因此，您需要 32 个字节来存储 bool visited[32]。

2. 位掩码是对此的空间优化。

让我们开始吧:

1. 您正在遍历字符串中的所有字符。
2. 假设在第 i 次迭代中您找到了字符“b”。 您计算其基于 0 的索引。

int val = str.charAt(i) - 'a';

'b' 为 1。即 98-97。

1. 现在使用左移运算符，我们找到 2^1 => 2 的值。

(1 << val) // 1<<1 => 10(binary)

现在让我们看看按位 & 是如何工作的

0 & 0 -> 0
0 & 1 -> 0
1 & 0 -> 0
1 & 1 -> 1

所以通过下面的代码:

(checker & (1 << val))

我们检查 checker[val] == 0 是否。 假设我们已经遇到了'b'。

check = 0000 0000 0000 0000 0000 1000 1000 0010   &  
'b'   = 0000 0000 0000 0000 0000 0000 0000 0010 
 ----------------------------------------------
result= 0000 0000 0000 0000 0000 0000 0000 0010

即十进制值 = 2 即 >0

所以你终于明白了这部分。

 if ((checker & (1 << val)) > 0) 
                return false;

1. 现在，如果没有遇到“b”，那么我们使用按位或设置检查器的第二位。

(这部分称为位掩码。)

OR 的真值表

0 | 0 -> 0
0 | 1 -> 1
1 | 0 -> 1
1 | 1 -> 1

所以

check = 0000 0000 0000 0000 0000 1000 1000 0000   |  
'b'   = 0000 0000 0000 0000 0000 0000 0000 0010 
 ----------------------------------------------
result= 0000 0000 0000 0000 0000 1000 1000 0010

这样就简化了这部分:

checker |= (1 << val);  // checker = checker |  (1 << val);

我希望这对某人有所帮助!