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; }Al igual que en el código anterior, ¿cómo funciona xor para obtener el número de ocurrencias de un número impar en una matriz?
Este código no cuenta el número de ocurrencias de un número impar. En su lugar, encuentra un solo número en una matriz que aparece un número impar de veces.
Su matriz de prueba tiene estos números:
2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2Sus conteos son los siguientes:
2 - 4 times 3 - 2 times 4 - 4 times 5 - 3 timesSolo 5 aparece un número impar de veces.
XOR tiene estas dos propiedades:
Y ^ 0 = Y X ^ X ^ Y = Y para cualquier valor de X e Y. En otras palabras, XOR-ing cualquier número Y con cero deja el valor sin cambios, y XOR-ing un número X dos veces con cualquier valor Y deja ese valor original sin cambios. El orden de las operaciones no importa. Dado que res comienza en cero, XOR-ing junta todos los números de su matriz produce 5, el único valor que no se XOR-ed un número par de veces.
No es asi. res += ar[i] & 1 ; cuenta, sin embargo.
Xor no genera un acarreo, por lo que no puede contar más de 1 bit:
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) Sin embargo, produce la paridad lineal (paridad en todos los bits en la misma posición (es decir, paridad para todos los bits 7, todos los bits 6, ...). El resultado de cualquier bit en res es 1 si la suma de todos los bits en ar con el mismo índice de bits es impar.
Combinado con una paridad en cada byte, da como resultado una matriz en la que se puede detectar y corregir un error de un solo bit, mientras que se puede detectar un error de dos bits (pero no corregir).
Esto se usó en días anteriores como una corrección de errores hacia adelante (débil) para algunos protocolos de transmisión. Hoy en día, existen algoritmos mejores, pero mucho más intensivos en procesamiento, como el código Hamming.
Editar:
Otros comentarios y respuestas sugieren que esto es para encontrar el valor único con apariencia extraña. Como esto impone bastantes restricciones en la entrada, no tiene un uso real y es puramente artificial. Sin embargo, la aplicación anterior definitivamente es real (o lo ha sido).
No los cuenta. Está utilizando un 'truco' eficiente para identificar la única instancia de un número con ocurrencias impares en una lista. Este truco no funcionaría si hubiera varios o ningún número que se presentara un número impar de veces.
Si xor un número consigo mismo, es igual a 0. Esta propiedad es válida incluso en múltiples operaciones, es decir, 3 ^ 4 ^ 3 ^ 4 = 0. Por lo tanto, en tal secuencia el resultado final será igual a cualquier número que no 't 'cancelar'. es decir, 3 ^ 4 ^ 3 = 4.