位操作和 XOR
Bit Manipulation and XOR
我有一个关于算法中位操作的问题。
给定一个整数数组,数组中的每个元素出现三次,除了一个元素只出现一次。找到只出现一次的那个元素。
示例:
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;
,但它显示了以下我无法理解的输出。这如何导致解决方案?
1 0
3 0
7 0
4 3
4 0
6 0
4 2
5 0
4 1
4 0
这段代码的作用是并行计算每个位的出现次数,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 位
我有一个关于算法中位操作的问题。
给定一个整数数组,数组中的每个元素出现三次,除了一个元素只出现一次。找到只出现一次的那个元素。
示例:
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;
,但它显示了以下我无法理解的输出。这如何导致解决方案?
1 0
3 0
7 0
4 3
4 0
6 0
4 2
5 0
4 1
4 0
这段代码的作用是并行计算每个位的出现次数,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