c++ - bitwise operators python
XOR Operation Intuition (6)
A ^ 0 == AA ^ A == 0A ^ B == B ^ A(A ^ B) ^ C == A ^ (B ^ C)
(3) y (4) juntos significan que el orden en el que los números se xor no importa.
Lo que significa que, por ejemplo, A^B^X^C^B^A^C es igual a A^A ^ B^B ^ C^C ^ X
Debido a (2) que es igual a 0^0^0^X
Debido a que (1) es igual a X
No creo que haya palabras clave específicas que puedan ayudarlo a identificar dichos problemas. Solo debes saber las propiedades anteriores de XOR.
Hace poco encontré this pregunta en Leetcode y descubrí una solución con la que necesito cierta aclaración:
Dado un conjunto de enteros, cada elemento aparece dos veces, excepto uno. Encuentra ese solo.
Nota: Su algoritmo debe tener una complejidad de tiempo de ejecución lineal. ¿Podrías implementarlo sin usar memoria extra?
class Solution {
public:
int singleNumber(vector<int>& nums) {
int result = 0;
for(auto & c : nums) {
result ^= c;
}
return result;
}
};
En primer lugar, ¿a qué tipo de palabras clave debo prestarle atención para descubrir que debería usar una operación XOR para esta pregunta?
Además, ¿por qué XOR''ing todos los elementos en el vector entre sí nos dan el que no se repite?
Gracias a todos por estas respuestas, aquí hay más información sobre propiedades bit a bit para cualquier otra persona interesada: Más información a nivel de bit
Como estoy seguro de que está familiarizado con, los enteros se almacenan en la memoria como tuplas de dígitos binarios. Uno puede ver cada dígito como un número en el campo de dos elementos, que es esencialmente enteros módulo 2. El operador ^ es componente-sabio xor, y con esta interpretación, xor es simplemente suma . Es decir, estamos agregando los dígitos binarios entre sí.
En este campo, 1 + 1 = 0, entonces uno puede decir que dos es cero. Como la adición es conmutativa y asociativa, podemos combinar todos los números a la vez. Cualquier cosa que se agregue un número par de veces no agregará nada, y solo el número que se agrega una sola vez termina en la variable de resultado.
Puede ser interesante saber que las operaciones booleanas se representan de esta forma como (¡pruébalo!): A xor b = a + b, a y b = ab, a o b = ab + a + b, no a = a + 1.
El aspecto intuitivo clave que distingue a XOR de los otros operadores lógicos es que es sin pérdida , o sin pérdida , lo que significa que, a diferencia de AND y OR (y más similar a NOT en este sentido), es determinísticamente reversible: puede exactamente recuperar uno de los valores de entrada dado el resto del historial de computación.
Los siguientes diagramas ilustran que AND y OR tienen al menos un caso en el que el estado de una de las entradas es irrecuperable, dado un cierto valor de la otra entrada. Indico estas como entradas "perdidas".
Para la puerta XOR , no hay ninguna condición en la que un valor de entrada o salida no se pueda recuperar, dado el resto del historial de computación. De hecho, existe una simetría que al conocer dos valores del triple (in0, in1, out) permite recuperar el tercero. En otras palabras, independientemente de la entrada o salida, cada uno de estos tres valores es el XOR de los otros dos.
Esta imagen sugiere que otra forma de pensar en la operación XOR es como una puerta NOT controlable . Al alternar una de las entradas (la superior en el ejemplo anterior), puede controlar si la otra (inferior) se niega o no.
Otra visión equivalente es que XOR implementa la función positive-logic no igual (≠) con respecto a sus dos entradas. Y así también la función igual (=) bajo negative-logic .
De acuerdo con sus propiedades de simetría y conservación de la información, XOR debería venir a la mente para problemas que requieren reversibilidad o recuperación de datos perfecta. El ejemplo más obvio es que XOR ing un conjunto de datos con una "clave" constante oscurece trivialmente los datos de forma que al conocer la clave (que podría mantenerse "en secreto"), permite una recuperación exacta.
Preservar toda la información disponible también es deseable en hashing . Como desea valores de hash que discriminen al máximo entre los elementos de origen, debe asegurarse de que se incorporen tantas de sus características distintivas como sea posible, minimizando la pérdida, en el código hash. Por ejemplo, para dividir un valor de 64 bits en 32 bits, usaría el operador XOR del lenguaje de programación ^ porque es una manera fácil de garantizar que cada uno de los 64 bits de entrada tenga la oportunidad de influir en el resultado:
uint GetHashCode(ulong ul)
{
return (uint)ul ^ (uint)(ul >> 32);
}
Tenga en cuenta que en este ejemplo, la información se pierde aunque se usó XOR . (De hecho, la ''pérdida de información estratégica'' es una especie de problema de hashing). El valor original de ul no es recuperable del código hash, porque con ese valor solo no tiene dos de los tres valores de 32 bits que se usaron en el cálculo interno. Recuerde que debe retener dos de los tres valores para una reversión perfecta. Fuera del código hash resultante y de los dos valores que fueron XOR ed, puede haber guardado el resultado, pero normalmente no guarda ninguno de estos últimos para usar como valor clave para obtener el otro. 1
Como un lado divertido, XOR fue especialmente útil en los días de los hackeos bits-twiddling . Mi contribución en aquel entonces fue una forma de configurar o borrar condicionalmente bits sin ramificar en C / C ++:
unsigned int v; // the value to modify
unsigned int m; // mask: the bits to set or clear
int f; // condition: 0 to ''set'', or 1 to ''clear''
v ^= (-f ^ v) & m; // if (f) v |= m; else v &= ~m;
En una nota más seria, el hecho de que XOR no tiene pérdidas tiene importantes implicaciones information-theoretical para la computación futurista, debido a una importante relación entre el procesamiento de la información y la Segunda Ley de la Termodinámica . Como se explica en un excelente y accesible libro de Charles Seife, Decoding the Universe , resulta que la pérdida de información durante el cálculo tiene una relación matemática exacta con la radiación del cuerpo negro emanada por un sistema de procesamiento. De hecho, la noción de entropy desempeña un papel central en la cuantificación de cómo la "pérdida" de información se (re) expresa como calor (que también es la misma relación prominente de la famosa apuesta de agujero negro de Steven Hawking).
Tal charla sobre XOR no es necesariamente un tramo; Seife señala que el desarrollo de CPU moderno actualmente enfrenta limitaciones de tolerancia fundamentales en los vatios / cm² de los materiales semiconductores, y que una solución sería diseñar sistemas informáticos reversibles o sin pérdidas. En esta generación futura especulativa de CPU, la capacidad de XOR de preservar la información y, por lo tanto, desviar el calor, sería inestimable para aumentar la densidad computacional (es decir, MIPS / cm²) a pesar de tales limitaciones de materiales.
ulong . Por supuesto, los "datos" hash originales en sí, representados por ul aquí, probablemente se conserven. El operador Xor es conmutativo :
1. X ⊕ Y = Y ⊕ X for any integers X and Y
y asociativo :
2. X ⊕ (Y ⊕ Z) = (X ⊕ Y) ⊕ Z for any integers X, Y and Z
Se deduce que el resultado de cualquier secuencia de operaciones xor es completamente independiente del orden de los operandos (es decir, el orden de los elementos en la matriz).
3. X ⊕ X = 0 for any integer X
4. X ⊕ 0 = 0 ⊕ X = X for any integer X
En el problema, tenemos una expresión donde cada elemento Ai aparece dos veces, excepto algún elemento singular B. La operación Xor resultante es equivalente a:
(A1 ⊕ A1) ⊕ (A2 ⊕ A2) ⊕ ... ⊕ B
=
0 ⊕ 0 ⊕ ... ⊕ B
=
B
a qué tipo de palabras clave debo prestarle atención para descubrir que debería estar usando una operación XOR para esta pregunta
Algunos problemas pueden resolverse rápidamente usando la manipulación de bits. Después de familiarizarse con los operadores booleanos y sus propiedades, y de ver suficientes aplicaciones como esta, naturalmente "sentirás" cuando sean útiles para resolver un problema determinado.
Una operación simple que se puede hacer en la matriz es elegir una propiedad P y contar la cantidad de elementos de la matriz que satisfacen la propiedad. Por ejemplo, si P tiene la propiedad de ser divisible por 5, podemos recorrer la matriz y contar el número de elementos que son divisibles por 5.
La precondición en la matriz nos permite obtener información sobre el elemento singleton a partir de dicha cuenta. Si el número de elementos que satisfacen P es impar, entonces el singleton tiene la propiedad P Si el número de elementos que satisfacen P es par, entonces el singleton no debe tener la propiedad P Por ejemplo, si contamos 3 elementos divisibles por 5, entonces el singleton debe haber sido divisible por 5.
Por lo tanto, si podemos inventar una colección de propiedades de modo que saber si cada propiedad es verdadera o falsa especificará completamente cualquier elemento, podemos obtener la respuesta contando el número de elementos con cada propiedad y verificando la paridad de los conteos.
Hay muchas colecciones diferentes de propiedades que funcionarán. Sin embargo, podemos ser eficientes. Dadas las diferentes propiedades, hay (como máximo) 2**b diferentes formas en que las pruebas pueden aparecer, por lo que solo podemos distinguir entre estos muchos elementos posibles. Por lo tanto, necesitamos al menos b propiedades diferentes para especificar por completo un número bbit.
Una de estas colecciones mínimas de propiedades que es fácil de probar para una computadora es la colección donde la n ésima propiedad es "¿Tiene el número un 1 en el n ésimo bit?". Si conocemos la respuesta a esta pregunta para cada n , entonces claramente podemos reconstruir el número.
Otra optimización es que no tenemos que hacer un seguimiento del recuento total de elementos que satisfacen una propiedad; solo necesitamos la paridad. Si hacemos un seguimiento del recuento módulo 2, solo necesitamos un bit para realizar un seguimiento en lugar de un size_t completo_t.
Como estamos haciendo un seguimiento de diferentes bits de información, cada uno correspondiente a un valor de lugar particular n , podemos agrupar estos bits en un número de bits b .
Esta es exactamente la solución XOR presentada en la pregunta.
Para comenzar, el recuento de cuántos números tiene cada bit es 0 para cada bit (por result tanto, el result se inicializa en 0). Entonces, cuando XOR un elemento de la matriz, en realidad estamos agregando un módulo 2 a los bits de result donde el elemento tenía un 1. Finalmente, el result no requiere ninguna decodificación, ya que el número con 1 bit exactamente donde el result tiene 1 bits es el result sí mismo.
XOR siempre se define en términos de dígitos binarios (o algunas nociones equivalentes, como declaraciones verdaderas o falsas). No hay ningún XOR especial para enteros distintos al XOR de los bits correspondientes de sus representaciones binarias.
Deje que A y B sean dos variables booleanas, y que XOR sea una función booleana que tome dos variables booleanas.
A⊕B = 1 si cualquiera (A = 0 y B = 1) o (A = 1 y B = 0) (es decir, son diferentes),
A⊕B = 0 si cualquiera (A = 0 y B = 0) o (A = 1 y B = 1). (es decir, son lo mismo)
Por lo tanto, teniendo en cuenta su pregunta ya que de n elementos del vector, cada elemento aparece dos veces excepto un elemento, la idea es que la representación binaria de los números duplicados sería la misma, por lo tanto, el resultado de XOR se anularía entre sí como 1⊕1 = 0 y 0⊕0 = 0.
Para A = 5, su representación binaria es 101, por lo que A⊕A = (101) ⊕ (101) = 000 que es la representación decimal es 0.
RECUERDE QUE NO IMPORTA EN QUE ORDEN LOS NÚMEROS APARECEN DESPUÉS DE UNO A OTRO PORQUE ((A⊕B) ⊕C) = (A⊕ (B⊕C)). Eventualmente, lo que obtienes al final después de XORAR cada número es el número que aparece una vez.
Para responder a su pregunta con respecto a cuándo necesita usar las operaciones XOR para resolver una pregunta, practique alguna pregunta sobre la MANIPULACIÓN DE BITS y eventualmente podrá averiguarlo.
Una sugerencia: la pregunta que pide encontrar un elemento que tenga una propiedad única aparte del resto, requiere la manipulación de bits.
Ejemplo: Dada una matriz donde cada elemento aparece tres veces, excepto un elemento que aparece solo una vez. Encuentra el elemento que ocurre una vez.