使用 XOR 和补码解析位

当向量中的所有其他数字恰好出现三次时，我无法找到仅出现一次的数字。

class Solution {
public:
    int singleNumber(vector<int>& nums) {

        int ones = 0;
        int twos = 0;

        for(const int& n : nums)
        {
            ones = (ones ^ n) & ~twos;
            twos = (twos ^ n) & ~ones;


            std::cout << ones << "\t" << twos << "\n";
        }

        return ones;
    }
};

对于输入 2,2,5,5,9,2,5 而言ones and twos在不同的过程中获取这些值

Ones Twos
2     0
0     2
5     2
0     7
8     6
8     4
9     0

我的问题是我怎么知道该算法会起作用，因为异或和补码会产生如下值0 7 , 8 4 and 8 6在两次传递之间，这些传递甚至不在正在解析的整数值中。

我不明白这里的定理是什么，它确保所有这些中间值最终都会减少到仅在输入向量中出现一个的值。我如何完全确定所有这些中间结果都会被清除并最终成为我想要检测的值。

谁能解释一下吗？

我只是明白ones = (ones ^ n) & ~twos;意味着添加到ones如果它不存在于twos and twos = (twos ^ n) & ~ones;意味着添加到twos如果它不存在于ones。这就是我所理解的。我不明白中间不相关的值背后的逻辑，让位于结果值。

计算结果令人困惑ones使用现有值进行更新twos but twos使用更新后的值进行更新ones在每次迭代中。

尝试绘制这样的跟踪表（前 3 列是十进制，后 6 列是二进制）：

要计算第 7 列的新值，请对第 4 列和第 6 列执行按位与操作。要计算第 9 列的新值，请对第 5 列和第 8 列执行按位 AND。将第 7 列和第 9 列的二进制值移至新行。

您还可以为每个列创建临时变量，并将它们的值包含在调试输出中。