math - bitwise - ¿Qué significa "XOR a nivel de bit"(OR exclusivo)?

bitwise operators javascript (7)

Estoy tratando de entender los operadores binarios en C # o, en general, en particular ^ - exclusivo o .

Por ejemplo:

Dada una matriz de enteros positivos. Todos los números ocurren incluso una cantidad de veces, excepto un número que ocurre un número impar de veces. Encuentra el número en O (n) tiempo y espacio constante.
Esto se puede hacer con ^ de la siguiente manera: Realizar un XOR bit a bit de todos los elementos. Finalmente obtenemos el número que tiene ocurrencias impares.

¿Como funciona?

Cuando lo hago:

int res = 2 ^ 3; res = 1; int res = 2 ^ 5; res = 7; int res = 2 ^ 10; res = 8;

¿Qué está pasando realmente? ¿Cuáles son los otros bits mágicos? ¿Alguna referencia que pueda buscar y aprender más sobre ellos?

Esto se basa en el simple hecho de que XOR de un número consigo mismo resulta cero.

y XOR de un número con 0 da como resultado el número mismo.

Entonces, si tenemos una matriz = {5,8,12,5,12}.

5 está ocurriendo 2 veces. 8 está ocurriendo 1 veces. 12 está ocurriendo 2 veces.

Tenemos que encontrar el número que se produce un número impar de veces. Claramente, 8 es el número.

Comenzamos con res = 0 y XOR con todos los elementos de la matriz.

int res=0; for(int i:array) res = res ^ i;

1st Iteration: res = 0^5 = 5 2nd Iteration: res = 5^8 3rd Iteration: res = 5^8^12 4th Iteration: res = 5^8^12^5 = 0^8^12 = 8^12 5th Iteration: res = 8^12^12 = 8^0 = 8

La definición del operador XOR (OR exclusivo), sobre bits, es que:

0 XOR 0 = 0 0 XOR 1 = 1 1 XOR 0 = 1 1 XOR 1 = 0

Una de las formas de imaginarlo es decir que el "1" en el lado derecho cambia el bit desde el lado izquierdo, y 0 en el lado derecho no cambia el bit en el lado izquierdo. Sin embargo, XOR es conmutativa, entonces lo mismo es cierto si los lados están invertidos. Como cualquier número puede representarse en forma binaria, dos números pueden ser XOR-ed juntos.

Para demostrar que es conmutativo, simplemente puede ver su definición, y ver que para cada combinación de bits en cada lado, el resultado es el mismo si se cambian los lados. Para demostrar que es asociativo, simplemente puede ejecutar todas las combinaciones posibles de tener 3 bits siendo XOR-ed entre sí, y el resultado se mantendrá igual sin importar cuál sea el orden.

Ahora, como demostramos lo anterior, veamos qué sucede si XOR el mismo número en sí mismo. Dado que la operación funciona en bits individuales, podemos probarla en solo dos números: 0 y 1.

0 XOR 0 = 0 1 XOR 1 = 0

Entonces, si XOR un número en sí mismo, siempre obtienes 0 (lo creas o no, pero esa propiedad de XOR ha sido utilizada por los compiladores, cuando un 0 necesita ser cargado en un registro de CPU. Es más rápido realizar una operación de bit que insertar explícitamente 0 en un registro. El compilador solo producirá un código ensamblador para XOR un registro sobre sí mismo).

Ahora, si X XOR X es 0, y XOR es asociativo, y necesita averiguar qué número no se ha repetido en una secuencia de números donde todos los demás números se han repetido dos (o cualquier otra cantidad impar de veces). Si tuviéramos los números que se repiten juntos, XOR a 0. Cualquier cosa que sea XOR-ed con 0 se mantendrá. Entonces, de la secuencia de XOR-ing tal secuencia, terminará quedándose con un número que no se repite (o repite una cantidad par de veces).

La otra forma de mostrar esto es usar el álgebra de XOR; no necesita saber nada sobre bits individuales.

Para cualquier número x, y, z:

XOR es conmutativo: x ^ y == y ^ x

XOR es asociativo: x ^ (y ^ z) == (x ^ y) ^ z

La identidad es 0: x ^ 0 == x

Cada elemento es su propia inversa: x ^ x == 0

Dado esto, es fácil probar el resultado declarado. Considera una secuencia:

a ^ b ^ c ^ d ...

Como XOR es conmutativo y asociativo, el orden no importa. Así que ordena los elementos.

Ahora cualquier elemento adyacente idéntico x ^ x puede reemplazarse por 0 (propiedad autoinverse). Y cualquier 0 se puede eliminar (porque es la identidad).

Repita el mayor tiempo posible. Cualquier número que aparece un número par de veces tiene un número entero de pares, por lo que todos se vuelven 0 y desaparecen.

Finalmente, te queda solo un elemento, que es el que aparece un número impar de veces. Cada vez que aparece dos veces, esos dos desaparecen. Eventualmente te queda una ocurrencia.

[actualizar]

Tenga en cuenta que esta prueba solo requiere ciertas suposiciones sobre la operación. Específicamente, supongamos un conjunto S con un operador . tiene las siguientes propiedades:

Assocatividad: x . (y . z) = (x . y) . z x . (y . z) = (x . y) . z x . (y . z) = (x . y) . z para cualquier x , y , y z en S.

Identidad: existe un solo elemento e tal que e . x = x . e = x e . x = x . e = x e . x = x . e = x para todo x en S.

Cierre: para cualquier x y y en S, x . y x . y también está en S.

Auto inverso: para cualquier x en S, x . x = e x . x = e

Como resultado, no necesitamos suponer conmutatividad; podemos probarlo:

(x . y) . (x . y) = e (by self-inverse) x . (y . x) . y = e (by associativity) x . x . (y . x) . y . y = x . e . y (multiply both sides by x on the left and y on the right) y . x = x . y (because x . x = y . y = e and the e''s go away)

Ahora, dije que "no necesitas saber nada sobre bits individuales". Estaba pensando que cualquier grupo que satisfaga estas propiedades sería suficiente, y que ese grupo no necesariamente tiene que ser isomorfo para los enteros bajo XOR.

Pero @Steve Jessup me demostró que estaba equivocado en los comentarios. Si define la multiplicación escalar por {0,1} como:

0 * x = 0 1 * x = x

... entonces esta estructura satisface todos los axiomas de un espacio vectorial sobre los enteros mod 2.

Por lo tanto, cualquier estructura de este tipo es isomorfa a un conjunto de vectores de bits bajo el componente XOR.

Los operadores bit a bit tratan los bits dentro de un valor entero como una pequeña matriz de bits . Cada uno de esos bits es como un pequeño valor bool . Cuando utiliza el operador u operador exclusivo de bits, una interpretación de lo que hace el operador es:

para cada bit en el primer valor, alternar el bit si se establece el bit correspondiente en el segundo valor

El efecto neto es que un solo bit comienza en false y si el número total de "alternaciones" es par, seguirá siendo false al final. Si el número total de "alterna" es impar, será true al final.

Solo piensa en "una pequeña matriz de valores booleanos" y comenzará a tener sentido.

Para ver cómo funciona, primero debe escribir ambos operandos en binario, porque las operaciones a nivel de bits funcionan en bits individuales.

Luego puede aplicar la tabla de verdad para su operador particular. Actúa sobre cada par de bits que tienen la misma posición en los dos operandos (el mismo valor de posición). De modo que el bit más a la izquierda (MSB) de A se combina con el MSB de B para producir el MSB del resultado.

Ejemplo: 2^10 :

0010 2 XOR 1010 8 + 2 ---- 1 xor(0, 1) 0 xor(0, 0) 0 xor(1, 1) 0 xor(0, 0) ---- = 1000 8

Y el resultado es 8.

Sé que esta es una publicación bastante antigua, pero quería simplificar la respuesta ya que me encontré con ella mientras buscaba otra cosa.
XOR (eXclusivo O / cualquiera o), se puede traducir simplemente como activar / desactivar.
Que excluirá o incluirá los bits especificados.

Usando 4 bits (1111) obtenemos 16 posibles resultados de 0-15:

decimal | binary | expanded 0 | 0000 | 1 | 0001 | 2 | 0010 | 3 | 0011 | (1+2) 4 | 0100 | 5 | 0101 | (1+4) 6 | 0110 | (2+4) 7 | 0111 | (1+2+4) 8 | 1000 | 9 | 1001 | (1+8) 10 | 1010 | (2+8) 11 | 1011 | (1+2+8) 12 | 1100 | (4+8) 13 | 1101 | (1+4+8) 14 | 1110 | (2+4+8) 15 | 1111 | (1+2+4+8)

El valor decimal a la izquierda del valor binario, es el valor numérico utilizado en XOR y otras operaciones bit a bit.

Por ejemplo: 0011 son los bits 1 y 2 como on, dejando los bits 4 y 8 como off. Que se representa como el valor decimal de 3 para indicar los bits que están encendidos, y se muestra en una forma expandida como 1+2 .

En cuanto a lo que está sucediendo con la lógica detrás de XOR aquí hay algunos ejemplos
Desde la publicación original

2 ^ 3 = 1
2 es miembro de 1 + 2 (3) eliminar 2 = 1
2 ^ 5 = 7
2 no es miembro de 1 + 4 (5) agregue 2 = 1 + 2 + 4 (7)
2 ^ 10 = 8
2 es miembro de 2 + 8 (10) eliminar 2 = 8

Otros ejemplos

1 ^ 3 = 2
1 es miembro de 1 + 2 (3) eliminar 1 = 2
4 ^ 5 = 1
4 es miembro de 1 + 4 (5) eliminar 4 = 1
4 ^ 4 = 0
4 es un miembro de sí mismo eliminar 4 = 0
1 ^ 2 ^ 3 = 0
Lógica: ((1 ^ 2) ^ (1 + 2))
(1 ^ 2) 1 no es miembro de 2 agrega 2 = 1 + 2 (3)
(3 ^ 3) 1 y 2 son miembros de 1 + 2 (3) eliminar 1 + 2 (3) = 0
1 ^ 1 ^ 0 ^ 1 = 1
Lógica: (((1 ^ 1) ^ 0) ^ 1)
(1 ^ 1) 1 es miembro de 1 eliminar 1 = 0
(0 ^ 0) 0 es miembro de 0 eliminar 0 = 0
(0 ^ 1) 0 no es miembro de 1 agrega 1 = 1
1 ^ 8 ^ 4 = 13
Lógica: ((1 ^ 8) ^ 4)
(1 ^ 8) 1 no es miembro de 8 agrega 1 = 1 + 8 (9)
(9 ^ 4) 1 y 8 no son miembros de 4 agrega 1 + 8 = 1 + 4 + 8 (13)
4 ^ 13 ^ 10 = 3
Lógica: ((4 ^ (1 + 4 + 8)) ^ (2 + 8))
(4 ^ 13) 4 es miembro de 1 + 4 + 8 (13) elimina 4 = 1 + 8 (9)
(9 ^ 10) 8 es miembro de 2 + 8 (10) eliminar 8 = 2
1 no es miembro de 2 +8 (10) agregue 1 = 1 + 2 (3)
4 ^ 10 ^ 13 = 3
Lógica: ((4 ^ (2 + 8)) ^ (1 + 4 + 8))
(4 ^ 10) 4 no es miembro de 2 + 8 (10) agregue 4 = 2 + 4 + 8 (14)
(14 ^ 13) 4 y 8 son miembros de 1 + 4 + 8 (13) eliminar 4 + 8 = 1
2 no es miembro de 1 ~~+ 4 + 8~~ (13) agregue 2 = 1 + 2 (3)

This tiene muchas muestras de varias funcionalidades hechas por medio de un toque de bits. Algunos de ellos pueden ser bastante complejos, así que ten cuidado.

Lo que necesita hacer para comprender las operaciones de bits es, al menos, esto:

los datos de entrada, en forma binaria
una tabla de verdad que te dice cómo "mezclar" las entradas para formar el resultado

Para XOR, la tabla de verdad es simple:

1^1 = 0 1^0 = 1 0^1 = 1 0^0 = 0

Para obtener el bit n en el resultado, aplique la regla a los bits n en la primera y segunda entrada.

Si intenta calcular 1^1^0^1 o cualquier otra combinación, descubrirá que el resultado es 1 si hay un número impar de 1 y 0 en caso contrario. También descubrirá que cualquier número XOR''ed con sí mismo es 0 y que no importa en qué orden haga los cálculos, por ejemplo 1^1^(0^1) = 1^(1^0)^1 .

Esto significa que cuando XOR todos los números en su lista, los que son duplicados (o presentan un número par de veces) XOR a 0 y se quedará con el que está presente un número impar de veces.