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)是如何工作的吗？以及'if'陈述.

Answer 1

我也正在阅读这本书Cracking the Code Interview,最后搜索了一个明确的解释.最后我理解了这个概念.

这是方法.

注意 :

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

2. Java 整数大小为32

3. 小写字母的数量是26

所以我们可以用十进制表示法在一个整数内清楚地设置0/1(真或假)值.

4. 它类似于bool访问[32]. bool使用1个字节.因此,您需要32个字节来存储访问的bool [32].

5. 位屏蔽是对此的空间优化.

开始吧 :

1. 您循环遍历字符串中的所有字符.
2. 假设在第i次迭代时你发现了字符'b'.您计算其基于0的索引.

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

对于'b',它是1.即66-65.

3. 现在使用左移运算符,我们找到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;

4. 现在如果没有遇到'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);

我希望这有助于某人!

Answer 2

好像我参加晚会晚了，但让我为解释解释一点点。

首先，AND即＆运算：

0 & 0 = 0
1 & 0 = 0
0 & 1 = 0
1 & 1 = 1

因此，基本上，如果给定一点，并且想知道它是1还是0，则将其与1匹配。如果结果为1，则您有1，否则您有0。我们将使用它＆以下的属性。

OR即| 操作

0 | 0 = 0
1 | 0 = 1
0 | 1 = 1
1 | 1 = 1  

因此，基本上，如果给了您一点点，并且您想要对其做一些事情，以使输出始终为1，则可以执行| | | | | | | | | | | | |，它们，它们分别是：1。

现在，在Java中，类型int为4字节，即32位。因此，我们可以将int自身用作数据结构，以更简单的方式存储32个状态或布尔值，因为位可以是0或1，即false或true。由于我们假定字符串仅由小写字符组成，因此我们在int内有足够的空间来为26个字符中的每个字符存储一个布尔值！

因此，首先我们初始化我们的数据结构，checker将其调用为0，但只不过是32个零：0000000000000000000000。

到目前为止，一切都很好？

现在我们遍历字符串，对于每个字符，首先我们得到该字符的整数表示。

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

我们减去a它是因为我们希望我们的整数基于0。因此，如果vals：

a = 0 i.e. `0000000000000000000000`
b = 1 i.e. `0000000000000000000001`
c = 2 i.e. `0000000000000000000010`
d = 4 i.e. `0000000000000000000100`

现在，如上所示，a是32个零，但是其余字符具有单个1和31个零。因此，当我们使用这些字符时，left shift每个字符都加1，即（1 << val），因此每个字符都有一个1位和31个零位：

a = 1 i.e. `0000000000000000000001`
b = 2 i.e. `0000000000000000000010`
c = 4 i.e. `0000000000000000000100`
d = 8 i.e. `0000000000000000001000`

设置完成。现在我们做两件事：

1. 首先假设所有字符都不同。对于我们遇到的每个字符，我们都希望我们的数据结构（即检查器）具有该字符的1。因此，我们使用上面描述的OR属性在我们的数据结构中生成1，因此我们这样做：

   checker = checker | (1 << val);
   

因此，checker为遇到的每个字符存储1。

2. 现在我们来讨论字符可以重复的部分。因此，在执行步骤1之前，我们要确保检查器在与当前字符对应的位置上已经没有1。所以我们检查

   checker & (1 << val)
   

因此，借助上述AND属性，如果我们从此操作中获得1，则checker在该位置已经有1，这意味着我们之前必须已经遇到过此字符。因此我们立即返回false。

就是这样。如果所有＆检查都返回0，则最终返回true，表示没有字符重新排列。

Answer 3

1 << val是相同的2 to the degree of val。所以它是
一个在其二进制表示中只有一个 1 的数字（val+1如果从
数字的右侧向左侧数，则该数字位于位置 ）。

a |= b基本上意味着：从 二进制表示中设置a所有二进制标志/标志（并保留已设置的标志）。
ba