1

我只是想学习按位/移位操作。

我遇到了下面的程序，但不理解下面程序中的 AND 条件部分（checker & (1 << val)。最终值什么时候会大于 0？有人可以解释一下那里发生了什么吗？

样本输入：xyzz

样本输出：

8388608Value 0checker 0最终值

16777216Value 8388608checker 0最终值

33554432Value 25165824checker 0 最终值

33554432Value 58720256checker 33554432final value

public static boolean isUniqueChars(String str) {
        int checker = 0;
        for (int i = 0; i < str.length(); i++) {
            int val = str.charAt(i) - 'a';

            System.out.println((1 << val) + "Value");
            System.out.println((checker) + "checker");
            System.out.println(((checker & (1 << val))) + "final value\n");

            if ((checker & (1 << val)) > 0) {
                return false;
            } else {
                checker = checker | (1 << val);
            }
        }
        return true;
    }

}
4

2 回答 2

6

好的，只是为了确保您知道发生了什么：

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

假设使用英文字母表，这将取您（小写）字母的 char 值并减去 97（'a' 的 char 值）以产生一个介于 0 和 25 之间的数字。不要在大写字符上尝试此功能，除非.toLowerCase()在.charAt(i)

1 << valval向左位移 1位。例如，对于 'x' (120 - 97 = 23, so... 1 << 23)，二进制表示为00000000010000000000000000000000

好的，到目前为止和我在一起吗？

一开始，checker 的位都是 0，所以它是00000000000000000000000000000000

所以......让我们输入我们的数字而不是我们的变量。对于我们的x检查，因为未在检查器中设置第 23 位，所以checker & (1 << val)变为00000000000000000000000000000000 & 00000000010000000000000000000000等于。00000000000000000000000000000000

因此，一旦x处理完毕，我们将第 23 位添加到 checker 并移动到下一个字母：y 这一次，因为第 24 位未在 checker 中设置，所以checker & (1 << val)变为00000000010000000000000000000000 & 00000000100000000000000000000000等于。00000000000000000000000000000000

对于第一个z，checker & (1 << val)变为00000000110000000000000000000000 & 00000001000000000000000000000000等于00000000000000000000000000000000，因为位 25 未在检查器中设置。

对于第二个z，checker & (1 << val)变为00000001110000000000000000000000 & 00000001000000000000000000000000等于00000001000000000000000000000000（十进制 33554432 或 2^25），因为在检查器中设置了第 25 位，因此> 0is nowtrue并且函数返回false。

于 2013-04-09T19:06:56.043 回答
1

我认为您的函数所做的是检查输入字符串中的所有字符是否不同。如果相同（小写）字符出现多次，则返回 false。

该checker变量用作一种位图，用于累积到目前为止已出现的字符。数据类型int由 32 位组成，足以为每个字符分配一位 (26)。

该函数循环遍历 str 的所有字符。该行根据字符（'a' => 0、'b' => 1、'c' => 2 等）int val = str.charAt(i) - 'a';分配某种序数值。val

该表达式1 << val将 (0..25) 范围内的每个 val 分配给它的位位置。因此，字符 'a' 映射到 1 << 0 == 1 == 00000001，字符 'd' 映射到 1 << 3 == 00001000，依此类推。每个字符都分配有其唯一的位掩码，其中一个位被设置，所有其他位被清除。

如果设置的位也在检查器中设置，则表达式(checker & (1 << val))> 0 1 << val（请注意，检查器可能设置了多个位）。如果是这样，则当前迭代的字符出现得更早，并且该函数返回 false。否则，当前字符的位掩码通过按位或运算符添加|到充当累加器的检查器中。如果所有字符都已循环并且没有字符遇到两次，则该函数返回 true。请注意，该函数可能会忽略大写和其他字符。

于 2013-04-09T19:07:53.687 回答