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

Question

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

像上面的代码一样，异或如何工作以获取数组中奇数的出现次数？

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零使值保持不变，并对数字进行异或运算 X两次，任意值 Y保持原始值不变。操作顺序无关紧要。自 res从零开始，对数组中的所有数字进行异或运算会产生 5 - 唯一没有进行偶数次异或运算的值。