位操作和 XOR

Question

我有一个关于算法中位操作的问题。

给定一个整数数组，数组中的每个元素出现三次，除了一个元素只出现一次。找到只出现一次的那个元素。

示例：

Input : [1, 2, 4, 3, 3, 2, 2, 3, 1, 1]  
Output : 4

我遇到了使用 XOR 的解决方案，但我无法理解它。以下是解决方案：

int singleNumber(vector<int> A) {
    int first = 0;
    int second = 0;
    for(auto n:A){
        first = (first ^ n) & ~second;
        second = (second ^ n) & ~first;
    }
    return first;
}

谁能解释一下下面两行代码是如何工作的？

first = (first ^ n) & ~second;
second = (second ^ n) & ~first;

[已编辑]

我已经为循环中的每个迭代包含了 cout<<first<<" "<<second<<endl;，但它显示了以下我无法理解的输出。这如何导致解决方案？

Answer 1

这段代码的作用是并行计算每个位的出现次数，mod 3.

first的第n位和second的第n位一起构成了这个计数器。

看看当我把 first 和 second 的一点写在一起然后从新数字中合并一点时会发生什么。以下是所有可能性：

             secondfirst    00  01  10    00  01  10
                 new bit     0   0   0     1   1   1
first=first^new &~second     0   1   0     1   0   0
+ sec=sec^new & ~first      00  01  10    01  10  00

可以看到，当新数中对应的位为0时，这两个位保持不变。但是当新位为1时，它们会经历一个循环，返回00每 3 个步骤。如果 1 的个数是 3n+1，我们在 first

中剩下一个 1 位

位操作和 XOR

Bit Manipulation and XOR

c++

algorithm

xor

bitmask