Daily C/C++ 位运算的妙用

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;
    }
}