Daily C/C++ 位运算的妙用
这个文章的思路来自于今天的每日一题
虽然是有点脑筋急转弯的题目,不过看到这样巧妙的利用位运算我还是想来分享一下这个做法
题目大意就是数组中只有两个元素的个数是1,其他元素的个数都是2。也就是只有两个元素没有重复,叫我们找出这两个元素
这个是之前题的进阶版,如果只有一个元素没有重复,那我们可以把整个数组异或一遍,重复的元素就会相互抵消,最终就剩下了答案
对于这个题来说,我们都异或一遍以后,得到的是 x = x1 \oplus x2
那我们如何充分利用这里的信息呢
对于这个x中的任意一个1,代表的是原本的两数x1和x2在这对应位上是不同的,也就是一个取1,一个取0
那根据这个信息,我们就可以将整个数列分为两类
任意的数ai,如果ai在这一位上取1,我们就划分到第一类,如果取0,我们就划分到第二类
同时我们也知道,数组中其他的数都是成对出现的,也就是说当我们划分完这两类之后,结果就是x1与一系列的成对的数是一类,x2与一系列成对的数是第二类
那么我们把这两类数分别求异或和,最终的结果就是x1和x2
还有个小问题,就是之前说的对应位的问题,我们可以遍历每一位,也可以简单的用x & -x
得到最右的一位
当然,x是不会取0的,因为我们知道x1和x2肯定是不同的
最后是代码,综合理解一下
unsigned xor0 = 0;
for (const auto &x : nums) {
xor0 ^= x;
}
unsigned i = xor0 & (-xor0);
unsigned xor1 = 0, xor2 = 0;
for (const auto &x : nums) {
if (x & i) {
xor1 ^= x;
} else {
xor2 ^= x;
}
}
文章评论