XOR - El operador bit a bit mágico

Comprender la manipulación de bits proporciona nuevos enfoques que nunca supo que existían para resolver un problema en particular. Hagamos lo que sea necesario para comenzar a desarrollar este enfoque bit a bit.

En este artículo, discutiremos sobre los poderes mágicos del operador bit a bit XOR.

XOR es un operador realmente sorprendente. Nunca te puedes imaginar las cosas que nos permite hacer. Antes de ver lo que puede hacer, revisemos lo que ya sabemos sobre el operador.

Bitwise XOR ( ^ ) como los otros operadores (excepto ~) también toman dos patrones de bits de igual longitud. Si ambos bits en la posición comparada de los patrones de bits son 0 o 1, el bit en el patrón de bits resultante es 0; de lo contrario, 1.

En resumen, significa que devuelve 1 solo si exactamente un bit se establece en 1 de los dos bits en comparación (O exclusivo).
A = 5 = 0101, B = 3 = 0011
A ^ B = 0101 ^ 0011 = 0110 = 6

Eso era lo básico sobre XOR. ¡Ahora veamos todos los poderes mágicos que posee el operador XOR! Me gustaría explicarlos dando algunos problemas antes, que te ayudarán a entender las propiedades claramente.

Devuelve el 1 más a la derecha en la representación binaria de un número.

Ejemplo: para 1010, debe realizar algunas operaciones para dar 0010 como salida. Para 1100, debe dar 0100. De manera similar, para 0001, debe devolver 0001.

Intenta encontrar la solución tú mismo. La pista más importante que tiene es que puede hacerlo usando el operador (^). Una vez que haya terminado, desplácese hacia abajo.

Solución:

Para este problema, necesitas conocer una propiedad de la resta binaria. Compruebe si puede encontrar la propiedad en los ejemplos a continuación,

1000 – 0001 = 0111

0100 – 0001 = 0011

1100 – 0001 = 1011

La propiedad es que la diferencia entre un número binario n y n-1 es que todos los bits a la derecha del 1 más a la derecha se invierten, incluido el 1 más a la derecha. Usando esta sorprendente propiedad, podemos obtener nuestra solución como

x ^ (x & (x - 1))

La única forma en que puede comprender completamente cómo funciona la solución anterior es probándola con diferentes números binarios en una hoja de papel.

(Si tiene experiencia en informática y entendió todo lo que he dicho hasta ahora, ¡felicidades! Ahora ya sabe el 80% sobre una poderosa estructura de datos llamada Fenwick Tree o Binary Indexed Tree. Puede consultarla para aprender el 20% o déjame saber si quieres que mi próximo artículo sea sobre eso).

¡Interesante! ¿no es así? Veamos algunas características más.

Para una matriz dada de elementos repetidos, exactamente un elemento no se repite. Debe devolver el elemento no repetido. [1, 2, 5, 4, 6, 8, 9, 2, 1, 4, 5, 8, 9]

Puede consultar el ejemplo anterior. Tendrás que devolver 6.

Existe una solución de complejidad lineal.

Solución:

Este es un poco sencillo. Necesitarás conocer las siguientes propiedades

norte ^ norte = 0

norte ^ 0 = norte

Algoritmo:

Cree una variable v con valor 0. Itere sobre una matriz de i = 0 a i = n-1 Realice v ^ arr [i] y almacene el resultado en v para cada iteración. Devuelva v.

Entonces, para mi pregunta final, me gustaría plantearles un problema bastante desafiante. Este no requiere el uso de ninguna propiedad nueva de XOR además de las mencionadas anteriormente.

Escribe una función para determinar el número de bits necesarios para convertir el entero A en el entero B.

Entrada: 31, 14

Salida: 2

Explicación: Tienes 31 (11111) y 14 (01110). Para convertir 31 a 14 tendríamos que invertir el bit más a la izquierda y el bit más a la derecha de 31.

El número de bits necesarios para voltear es 2, por lo que devolvemos 2 como respuesta.

Entrada: 12, 7

Salida: 3

Le sugiero que intente implementarlo antes de ver la solución a continuación. ¡Buena suerte!

Si crees que esto te ha ayudado de alguna manera, dale me gusta y sígueme para obtener más información fascinante sobre informática.

Solución: