位运算(只出现一次的数字|||)(5)

一.题目260. 只出现一次的数字 III - 力扣LeetCode二.思路解决2.1 思路讲解首先我们可以通过异或运算把数组中的所有元素异或起来那么最终得到的结果就是两个只出现一次的元素的异或结果。这个结果有什么用呢关键在于异或结果中的每一个1都代表着这两个元素在该二进制位上的值不同一个是0一个是1。因此我们可以利用这个结果来区分这两个元素。接下来我们需要获取异或结果的最右边的 1也可以是任意一个1这个1标志着这两个元素的第一个不同之处。如何获取最右边的1这里有一个经典的位运算技巧xor -xor。公式推导在计算机中负数采用补码表示。对于一个整数x-x等于~x 1取反加一。当我们将x与-x进行按位与运算时结果恰好保留了x最右边的那个1而其他位全部变为0。例如x 1010 1100二进制则-x 0101 0100相与得到0000 0100即最右边的1所在的位置。这个技巧非常高效常用于树状数组等算法中。为什么要找最右边的1因为我们可以通过这个位将原数组分成两组一组是该位为1的元素另一组是该位为0的元素。这样两个只出现一次的元素就会被分到不同的组中而其他成对出现的元素也会被分到同一组中因为成对出现的元素在该位相同。然后我们分别对这两组进行异或运算。由于每组中除了一个只出现一次的元素外其他元素都出现两次因此异或的结果就是该组中那个只出现一次的元素。这样我们就得到了这两个数。三.代码演示class Solution { public: vectorint singleNumber(vectorint nums) { int n nums.size(); vectorint v1; vectorint v2; //找到两个元素的差异 int ret 0; for(const auto x:nums) { ret ret ^ x; } ret (ret INT_MIN ? ret :ret -ret);//获取最右边的1 //把和差异相同的放在一起即最右边是1的放一起0的放一起 for(const auto x:nums) { if(x ret) v1.push_back(x); else v2.push_back(x); } //清除各自数组相同元素 int sum1 0; int sum2 0; for(const auto x:v1) { sum1 sum1 ^ x; } for(const auto x:v2) { sum2 sum2 ^ x; } return {sum1,sum2}; } };四.代码讲解一、整体异或得到两个目标数的异或值首先我们需要找到数组中两个只出现一次的数字。由于其他数字都出现两次我们可以利用异或的自反性将数组中所有元素进行异或。遍历数组依次执行ret ret ^ x最终得到的ret就是这两个只出现一次的数字的异或结果。这个结果中为1的位表示这两个数字在该位上不同。二、提取最右边的 1 作为区分位为了将这两个数字分到不同的组中我们需要从ret中找到一个为 1 的位。通常选择最右边的 1因为它容易提取且不影响结果。提取最右边 1 的经典方法是ret -ret。其原理是负数的补码表示是原数取反加一与运算后恰好保留最低位的 1。但这里有一个特殊情况当ret等于 INT_MIN 时-ret在补码中等于自身因为溢出此时ret -ret仍然等于 INT_MIN不会出错。因此代码中使用了ret (ret INT_MIN ? ret : ret -ret)确保安全。三、根据区分位将原数组分为两组接下来我们再次遍历原数组根据每个元素与区分掩码ret的与运算结果将其分到两个不同的数组中如果x ret不为 0说明该元素在区分位上为1放入v1。否则说明该元素在区分位上为0放入v2。这样两个只出现一次的数字必然被分到不同的组因为它们在区分位上不同而其他成对出现的数字由于相同在区分位上也相同因此会被分到同一组且成对出现。四、分别对两组进行异或得到答案现在每一组中除了一个只出现一次的数字外其余都是成对出现的。因此我们分别对v1和v2中的所有元素进行异或就能得到该组中那个只出现一次的数字。定义sum1和sum2并初始化为 0分别遍历两个数组执行异或操作。最终sum1和sum2就是我们要找的两个数字。