带左移和校验字符串的位操作

Question

我正在编写一些代码来检查字符串中字符的重复。这是我在某处找到的一些答案。

int checker = 0, val =0, max = 0, j =0, count = 0;
        for(int i=0; i<s.size() && j<s.size(); i++)
        {
            j = i;
            while(j<s.size())
            {
                val = s[j]-'a';
                if ((checker & (1<<val)) >0) break;
                checker |= 1 << val;
                j++;
                count++;
            }
            if(count > max) max = count;
            checker = 0;
            count = 0;
        }
        return max;

方法简单明了。但是，我对两行感到困惑。

        val = s[j]-'a';
        if ((checker & (1<<val)) >0) break;
        checker |= 1 << val;

我不知道的是，val 是减法后的某个值。那么(1 << val)就是1左移val，我的理解是1*2^(val)。然后 1 << val 需要 =1 跳出循环。但是请问是怎么实现的呢？谢谢。

Answer 1

检查器从右到左的每一位都为找到的每个字符标记。比方说，如果在字符串中找到 b，则设置右起第二位。如果它是 c，则它是第三位……这个 checker 位掩码用于匹配后续字符。

Answer 2

一段一段：

设置val为当前字符-'a'，也就是说，'a'给出0，'z'25

val = s[j]-'a';

检查检查器中的位：如果位 val 已经在 checker 中设置，则中断。这是通过将值与位掩码进行逻辑与运算来实现的；如果设置了该位，则该值应为正（假设，假设）。

if ((checker & (1<<val)) >0) break;

否则通过 orring 将 val 位设置为 1。

checker |= 1 << val;

代码做了很多假设；例如 int 需要至少有 26 位，并且 'a' 之外的字符 - 字符串中的 'z' 可能会导致未定义的行为。

Answer 3

代码的作者使用变量 'checker' 作为位掩码来记住他已经看过的字符。该行：

val = s[j] - 'a';

将字符 s[j] 的 ASCII 值标准化为 'a' 的 ASCII 值。基本上，他是在计算这个字符在 [0, 25] 范围内的哪个字母表中的小写字母字符：a 是 0，b 是 1，c 是 2 等等。

然后他正在检查此位是否已在 'checker' 中设置。他通过将归一化值左移 1 并将其与 'checker.' 进行“与”运算来实现这一点。循环将继续。如果已设置，则 AND 将 return 非零，他的测试将打破循环。

当该位未设置时，他将设置 'checker' 中对应于该位置的位。如果字符是 'a'，则设置最低有效位，'b'，然后设置第二个最低有效位，依此类推，将左移 'val' 的 1 与现有 'checker'.

PS - 他本可以很容易地使 'checker' 成为 26 个字符的数组并完成：

char checker[26] = { 0 };
...
    while(j < s.size() && !checker[s[j] - 'a'])
    {
        checker[s[j] - 'a'] = 1;
        ++j;
        ++count;
    }
...

我相信你会明白这一点。这基本上就是他正在做的事情，只是将数组填充到一个位掩码中，而不是使用一些位操作。这样他也可以通过将检查器设置为零来轻松清除设置位。

Answer 4

您向我们展示的这段有趣的代码采用了一些假设：

字符串s只包含小写字母('a'..'z').
int 类型有 32 位（或更多）。

代码所做的是为目前找到的每个字符在检查器变量中设置一个位（26 个小写字符适合一些 31/32 位 int，1 位与一个字符相关联）。他最好使用一些 uint32_t，顺便说一句。

通过从当前字符中减去 'a' 如果他的字符串符合假设 1，他将得到值 (0..25)。

if() 表达式测试该位之前是否已设置，即该字符之前是否出现过。

无论在checker中设置哪一位，它都是!= 0。如果假设1成立，它总是> 0。（无法到达第31位，这是符号位。）

Answer 5

让我们逐行分解。

val = s[j]-'a';

这是一个巧妙的技巧，可以将 'a'->'z' 范围内的任何字符转换为数字 0-25。实际上，您通常将其视为 s-'0' 以将数字字符转换为数字，但它同样适用于字母。它利用了 ASCII/UTF8 字符 space 中的字母是连续的这一事实，因此如果将字符视为数字并减去起始字母，则会得到字符的 'offset' 'a' 为 0，'z' 为 25。

if ((checker & (1<<val)) >0) break;

这里的关键是理解 1<<val 会做什么。这将左移一个 1 位 val 位。因此，对于 'a'，您将得到 0b1，对于 'b'，您将得到 '0b10'，依此类推。实际上，它一次性将字母编码为 32 位整数中的一位。如果我们然后 & 这与我们的 checker 值，它记录了我们已经看到的相同的单热字母位域，结果值将是 >0 当且仅当 checker 在表示字母的位中包含一个 1。如果是这样，我们就找到了重复项，所以我们中断。

checker |= 1 << val;

如果我们到达此处，则意味着 checker 不包含该字母的位中的 1。所以我们现在已经看到了这封信，需要更新 checker。 |= 将其与之前的 val 一起使用将始终将该单个位设置为 1，同时保持任何其他位不变。

带左移和校验字符串的位操作

Bit manipulation with left shift and check string

c++

c

bit-manipulation