XOR如何在C中工作以查找出现奇数次数的数字？

int getOddOccurrence(int ar[], int ar_size) { int i; int res = 0; for (i=0; i < ar_size; i++) res = res ^ ar[i]; return res; } /* Diver function to test above function */ int main() { int ar[] = {2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2}; int n = sizeof(ar)/sizeof(ar[0]); printf("%d", getOddOccurrence(ar, n)); return 0; } 

与上面的代码一样，xor如何在数组中获取奇数的出现次数？

Answer 1

此代码不计算奇数出现的次数。 相反，它在数组中找到一个奇数次的数字。

您的测试数组包含以下数字：

 2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2 

他们的计数如下：

 2 - 4 times 3 - 2 times 4 - 4 times 5 - 3 times 

只有5个被列出奇数次。

XOR具有以下两个属性：

 Y ^ 0 = Y X ^ X ^ Y = Y 

对于任何X和Y的值，换句话说，将任何数字Y与零进行异或，使值保持不变，并且对任何值Y两次XOR异或，使原始值保持不变。 操作顺序无关紧要。 由于res从零开始，因此将数组中的所有数字进行异或运算产生5 – 唯一的值不是偶数次的异或。

Answer 2

它不算数。 它使用有效的“技巧”来识别列表中出现奇数的数字的单个实例。 如果有多个或没有数字出现奇数次，这个技巧就行不通。

如果你自己与一个数字x，它等于0.即使在多个操作中，该属性也成立，即3 ^ 4 ^ 3 ^ 4 = 0.因此，在这样的序列中，最终结果将等于任何数字’t’取消’。 即3 ^ 4 ^ 3 = 4。

Answer 3

它不是。 res += ar[i] & 1 ; 然而，确实很重要。

Xor不生成进位，因此它不能超过1位：

 I1 I2 I1^I2 0 0 0 0 1 1 1 0 1 1 1 0 I1: bit[k] of res I2: bit[k] of ar[i] k = 0 ... (sizeof(int) * CHAR_BIT - 1) (number of bits in int - 1) 

然而，它产生线性奇偶校验（在相同位置的所有位上的奇偶校验（即所有位7的奇偶校验，所有位6，……）。如果所有位的总和，则res中的任何位的结果为1 。具有相同位索引的ar是奇数。

结合每个字节的奇偶校验，它产生一个矩阵，可以检测和纠正单个位错误，同时可以检测到两位错误（但未校正）。

这在早些时候用作某些传输协议的（弱）前向纠错。 如今，有更好的，但更多的处理密集型算法，如汉明码。

编辑：

其他评论和答案表明这是找到奇怪外观的单一值。 由于这对输入提出了相当多的限制，因此它没有实际用途而且纯粹是人为的。 但是，上面的申请绝对是真实的（或已经）。

Answer 4

嗨，这是我的代码，找到两个奇数，这是我在大学里的实验室任务。 希望你能得到这个概念。

  void printTwoOdd(int arr[], int size) { int xor2 = arr[0]; /* Will hold XOR of two odd occurring elements */ int set_bit_no; /* Will have only single set bit of xor2 */ int i; int n = size - 2; int x = 0, y = 0; /* Get the xor of all elements in arr[]. The xor will basically be xor of two odd occurring elements */ for(i = 1; i < size; i++) xor2 = xor2 ^ arr[i]; /* Get one set bit in the xor2. We get rightmost set bit in the following line as it is easy to get */ set_bit_no = xor2 & ~(xor2-1); /* Now divide elements in two sets: 1) The elements having the corresponding bit as 1. 2) The elements having the corresponding bit as 0. */ for(i = 0; i < size; i++) { /* XOR of first set is finally going to hold one odd occurring number x */ if(arr[i] & set_bit_no) x = x ^ arr[i]; /* XOR of second set is finally going to hold the other odd occurring number y */ else y = y ^ arr[i]; } printf("\n The two ODD elements are %d & %d ", x, y); } 

这是主要方法

 void main() { int arr[] = {4, 2, 4, 5, 2, 3, 3, 1}; int arr_size = sizeof(arr)/sizeof(arr[0]); printTwoOdd(arr, arr_size); getchar(); }