基于异或(XOR)与取反(Complement)的位运算算法：中间值为何不影响结果？

核心逻辑：按位独立追踪次数 #

所有数的二进制位是独立的，我们只需要单独分析每一位的状态变化：

• 对于出现三次的数，它的每一位1会被累计3次，最终要清零；
• 对于只出现一次的数，它的每一位1会被累计1次，最终保留在结果中。

我们用ones和twos两个变量的每一位组合，来记录对应二进制位上1出现的次数状态：

• 状态0：ones位=0，twos位=0 → 该位累计0次1
• 状态1：ones位=1，twos位=0 → 该位累计1次1
• 状态2：ones位=0，twos位=1 → 该位累计2次1

当某一位第3次出现1时，状态从2重置回0，完成循环。

代码语句的状态转移逻辑 #

1. ones = (ones ^ n) & ~twos

• ones ^ n：尝试给当前位的计数加1（0变1，1变0），模拟"出现次数+1"的翻转；
• & ~twos：当twos的该位是1时（当前处于状态2），强制把ones的该位置0——也就是第3次遇到1时，直接清零ones，避免进入无效状态。
• 实际效果：
  • 状态0遇到1 → 转到状态1（ones位变1，twos位保持0）
  • 状态1遇到1 → ones位变0（为转到状态2做准备）
  • 状态2遇到1 → ones位保持0（直接重置回状态0）

2. twos = (twos ^ n) & ~ones

这一步是在更新完ones后，同步更新twos：

• twos ^ n：同样尝试翻转位，模拟计数变化；
• & ~ones：当ones的该位是1时（当前处于状态1），强制把twos的该位置0——避免twos和ones同时为1的无效状态。
• 实际效果：
  • 状态1遇到1 → 转到状态2（twos位变1，ones位已变0）
  • 状态2遇到1 → twos位变0（重置回状态0）
  • 状态0遇到1 → twos位保持0（停在状态1）

中间值的合理性 #

你看到的奇怪中间值（比如0与7、8与4的组合），是因为不同二进制位的状态可能不同：某几位处于状态1，某几位处于状态2，组合起来的数自然不在输入列表里。但因为每个输入数的所有位是同步处理的，当所有出现三次的数处理完成后，它们的每一位都会循环回状态0；而只出现一次的数的每一位会停留在状态1，此时ones就是目标数，twos会全为0，所有中间混合状态都会被清零。

举个简单例子：输入[2,2,2,3]（二进制10,10,10,11）

• 处理前3个2后，ones和twos都回到0；
• 处理3时，ones变成11（十进制3），twos保持0，最终得到正确结果。

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