找不同字符为什么可以用异或？异或如何抵消成对字符？

简化版

两个字符串 s 和 t 中，t 比 s 多一个字符。把两个字符串所有字符都异或起来，成对出现的字符会抵消成 0，最后剩下的就是多出来的字符。

详细版

异或满足 x ^ x = 0、x ^ 0 = x，并且交换律、结合律成立。因此字符顺序不重要，只要相同字符出现两次就会抵消。遍历 s 和 t 的所有字符，用一个变量 ans 累积异或，最后把结果转回字符。

时间复杂度 O(n)，空间复杂度 O(1)。这题也可以用计数数组，但异或写法更简洁，适合“只有一个额外元素”的模型。

完整版教学

一、题目结构为什么适合异或

t 是 s 打乱后额外加了一个字符。也就是说，除了多出来的那个字符，其他字符都能成对匹配。

s = "abcd"
t = "abcde"

把所有字符放到一起，a,b,c,d 都出现两次，只有 e 出现一次。

二、异或的抵消性质

异或有三条关键性质：

x ^ x = 0
x ^ 0 = x
x ^ y = y ^ x

这意味着相同元素无论隔多远，都能在整体异或里抵消。

表达式	结果
`a ^ a`	0
`a ^ b ^ a`	b
`a ^ b ^ b ^ c ^ a`	c

记忆钩子：异或适合“成双抵消，剩一个”的题。

三、为什么字符也能异或

字符在计算机里有编码值，比如小写字母可以看作整数。Java 中 char 可以参与位运算，会按编码值计算。

'a' ^ 'a' = 0

所以对字符异或，本质是在对它们的编码整数异或。最后把整数结果转回 char。

四、代码模板

char findTheDifference(String s, String t) {
    int ans = 0;
    for (char c : s.toCharArray()) ans ^= c;
    for (char c : t.toCharArray()) ans ^= c;
    return (char) ans;
}

也可以把两个循环合并，但分开写更清楚。

五、用例子推演

s="abc"，t="bcae"：

ans = a ^ b ^ c ^ b ^ c ^ a ^ e
    = (a^a) ^ (b^b) ^ (c^c) ^ e
    = e

因为异或满足交换律和结合律，字符顺序被打乱不影响结果。

六、和计数数组的对比

计数数组也能做：统计 t，减去 s，剩下计数为 1 的字符就是答案。

方法	空间	特点
异或	`O(1)`	简洁，适合单个额外字符
计数	`O(字符集)`	更通用，可处理多个差异

如果题目变成多出多个字符，异或就不够了，需要计数或哈希。

七、常见误区与追问

误区：认为异或只能用于数字。 字符也有编码值，可以参与位运算。
误区：担心字符串顺序不同。 异或满足交换律，顺序不影响抵消。
误区：多出多个字符也用同样方法。 多个剩余字符异或会混在一起，无法直接还原。
追问：为什么 x^x=0？ 每一位相同异或都为 0。
追问：和求和相减有什么区别？ 求和也能做，但异或不担心加和溢出且语义更贴合抵消。
追问：空间复杂度是多少？ 只用一个累积变量，是 O(1)。

八、加强记忆

找不同字符就是“多一个，其他都成双”。异或的天赋正是成双抵消：x^x=0，剩下谁，答案就是谁。只要题目保证只多一个元素，且元素可编码成整数，异或就是最短路径；一旦多出多个，就换计数。

简化版

详细版