关于Rust中位运算XOR与左移实现字符去重检测代码的疑问

核心思路 #

这种解法用32位整数作为位掩码，用每一位对应一个小写字母的存在状态（1表示存在，0表示不存在）——因为小写字母只有26个，32位完全足够覆盖。

左移操作的作用 #

左移1 << (c as u8 - b'a')是为每个字符生成唯一的位标记：

• 对于字符'a'，c as u8 - b'a'结果是0，1 << 0得到二进制000...0001，对应第0位为1；
• 字符'b'对应1 << 1，二进制000...0010，第1位为1；
• 以此类推，每个字母都对应掩码中唯一的一个位，用单个位就能标记该字符是否在当前窗口中。

XOR异或的工作逻辑 #

异或运算的规则是相同位上值相同则为0，不同则为1，这里用它来切换字符的存在状态：

• 如果字符之前没出现在窗口中（对应位为0），异或位标记后，该位会变成1（标记为已存在）；
• 如果字符之前已经在窗口中（对应位为1），异或位标记后，该位会变成0（标记为移除）。

这个特性完美适配滑动窗口场景：窗口右移加入新字符时用XOR标记，窗口左移移除旧字符时用XOR取消标记。

以'abcdefghijklmno'为例的计算验证 #

这个字符串前14个字符是a到n，每个字符对应不同的位：

• 逐个异或后，掩码的二进制是第0位到第13位全为1，其余位为0；
• 这个值的十进制是(1 << 14) - 1 = 16383，用mask.count_ones()会得到14，说明当前窗口有14个不同字符，符合要求。

如果你的计算结果不符，大概率是这两个问题：

1. 位位置计算错误：比如误将'a'对应第1位而不是第0位，导致所有位标记偏移；
2. 混淆异或与其他运算：比如用加法代替异或，重复字符会导致位被多次置1，无法正确标记重复。

典型Rust代码示例 #

fn find_14_unique_substring(s: &str) -> Option<&str> {
    let mut mask = 0u32;
    let mut left = 0;

    for (right, c) in s.chars().enumerate() {
        // 生成当前字符的位标记
        let bit = 1 << (c as u8 - b'a');
        // 切换当前字符的存在状态
        mask ^= bit;

        // 如果异或后该位为0，说明字符重复，移动左指针直到无重复
        while (mask & bit) == 0 {
            let left_char = s.chars().nth(left).unwrap();
            let left_bit = 1 << (left_char as u8 - b'a');
            mask ^= left_bit;
            left += 1;
        }

        // 检查窗口长度是否达到14
        if right - left + 1 == 14 {
            return Some(&s[left..=right]);
        }
    }

    None
}

这段代码中，当窗口内出现重复字符时，mask & bit会等于0（异或后该位被置0），此时通过左移窗口并异或移除旧字符，直到mask & bit恢复为1（窗口内无重复）。当窗口长度刚好14时，就找到了符合要求的子串。

内容的提问来源于stack exchange，提问作者MarinaF