使用xor解释在数组中找到两个非重复的整数
给定[1,1,4,5,5,6]我们可以发现4和6是非重复整数。
有一个使用XOR的解决方案 。
这是作者提出的算法：
#include #include /* This finction sets the values of *x and *y to nonr-epeating elements in an array arr[] of size n*/ void get2NonRepeatingNos(int arr[], int n, int *x, int *y) { int xor = arr[0]; /* Will hold xor of all elements */ int set_bit_no; /* Will have only single set bit of xor */ int i; *x = 0; *y = 0; /* Get the xor of all elements */ for(i = 1; i < n; i++) xor ^= arr[i]; /* Get the rightmost set bit in set_bit_no */ set_bit_no = xor & ~(xor-1); /* Now divide elements in two sets by comparing rightmost set bit of xor with bit at same position in each element. */ for(i = 0; i < n; i++) { if(arr[i] & set_bit_no) *x = *x ^ arr[i]; /*XOR of first set */ else *y = *y ^ arr[i]; /*XOR of second set*/ } }
我对4^6之后的内容感到困惑。 我很困惑set_bit_no如何工作（包括动机）以及之后的任何事情。
有人可以尝试用更简单的英语方式解释它吗？ 谢谢。
如果我们有重复的数字对，它们就不会向xor结果添加任何内容，因为它们的xor将为零。 只有一对不同的数字会将非零位添加到xor结果中。
a xor a = 0 [a, b, c, b, d, a] a xor b xor c xor b xor d xor a = c xor d
现在在c x或d中，唯一的设置位是c和d中不同的位。 假设第3位在c xor d中设置。 这意味着如果位3在c中为0，则在d中为1，反之亦然。
因此，如果我们将所有数字划分为2组，则包含所有数字的第3位为0，而其他第3位为1，则c和d肯定会转到不同的组。 并且所有相同数字对将成为同一组。 （比特3在a和0都是1或者两者都是0）
让我们说这些小组是
[aca] and [bdb] xoring them a xor c xor a = c (The first number) b xor d xor b = d (The second number)
团体的其他可能性是
[c] and [abdba] xoring them c = c (The first number) a xor b xor d xor b xor a = d (The second number)
和
[abcba] and [d] xoring them a xor b xor c xor b xor a= c (The first number) d = d (The second number)
关于
set_bit_no = xor & ~(xor-1);
如果输入数组由自然数组成，则xor将为正xor和~xor为零（定义为所有位都反转）从xor减去1，
- 如果最右边的位为零，则将其设置为1并退出
- 将最右边的位重置为零并尝试将1添加到下一位（步骤1）
简而言之，1的最右边的位将变为零（倒退，类似于xor），第一个（最右边）的零位将变为1（与xor相同）。 现在开始，这个新设置的1位的所有位在xor和〜（xor-1）中都是不同的，所以它们将生成0，所有新设置的1位都在xor和〜（xor- 1）因此它们将生成0.在两种情况下，只有位于〜（xor-1）中新设置1的位的位是1，因此只有这个位将在表达式xor＆〜（xor-1）中设置
这里解释的简单方法是，当你执行a^b只设置那些在a中具有不同值的位位置。 因此，如果您将数组中的元素与a^b中的特定设置位的值进行分组，那么a和b将在不同的组中作为xor，组将取消其他组，两个组的结果将为a和b。
示例： –
a = 4 b = 6 a^b = 2 Set_bit_pos = 1 Arr = [1,1,4,5,5,6] Grouping according to bit no 1 x = [6] where bit1 is 1 y = [4,1,1,5,5] where bit1 is 0 Xoring x = 6 y = 4^1^1^5^5 = 4
该算法仅在当前时才有效
1) elements are non-zero 2) contains no more than 2 non-repeating integers. If only 1 non-repeating, one of the result (x or y) will be 0. 3) the repeated numbers occurs in pairs (ie. 2,4,6....)
如果0是可能的数字，那么您无法区分找到的答案或没有答案。
通过对所有元素进行异或运算，可以得出2个非重复整数之间的差异（即示例中为4 ^ 6）。 这是因为所有其他元素都会重复（即偶数次），而在XOR中，它们会自行取消。 重要的是要注意XOR是可交换的（即，顺序与a ^ b = b ^ a无关）
现在是set_bit_no 。 这只是存储最右边的设置位或xor 。 为什么最合适？ 因为我猜很容易。 但是任何一点都行。 xor变量中的设置位包含4到6之间不同的位。
100 ^ 110 = 010
第二位是1，因为这是4和6之间的唯一位。类似地，3和8之间的差异
0011 ^ 1000 = 1011
显示第3位，第2位和第1位在3和8之间不同。
获取设置位并在if条件中使用它的原因是为了确保将答案（4和6）写入不同的变量（x或y）。 为什么这样做？ 因为set bit保证2个答案在该位位置包含不同的值。
if(arr[i] & set_bit_no)
当你xor两个相等的值时，它们会取消。 这允许揭示非重复对。
XOR(aabbccddeeffgh) = XOR(gh) = ...1...
知道g和h不同的任何位允许在两个子集中设置g和h ：
...0... => XOR(aabbcceeg) = g ...1... => XOR(ddffh) = h