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如何在数组中获取奇数的出现次数?

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

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

 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 – 唯一的值不是偶数次的异或。

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

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

它不是。 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是奇数。

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

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

编辑:

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

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

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