Lógica detrás de operadores bit a bit en C

Question

Me encontré con operaciones a nivel de bit en la programación de C, y me di cuenta de que operador XOR puede ser usado para intercambiar 2 números en sus binario bases. Por ejemplo supongamos $$i=(65)_{10}=(1000001)_{2}, \text{ and } j=(120)_{10}=(1111000)_{2}$$.

Deje $\oplus$ ser el operador XOR, luego de observar que si empecé con uno de ellos, decir $i$ y siguiendo el siguiente procedimiento:

1)reemplazar su valor con el $\oplus$ valor, produciendo $$i=(0111001)_{2},j=(1111000)_{2}$$

2) reemplazar a la otra variable($j$) con otro $\oplus$ valor derivado de la nueva $i$ y de edad $j$, produciendo $$i=(0111001)_{2},j=(1000001)_{2}$$

3)reemplazar el original de la variable $i$ $\oplus$ valor de nuevo, produciendo $$i=(1111000)_{2},j=(1000001)_{2}$$

lo que demuestra que de alguna manera tienen sus valores intercambiados. He encontrado esta forma de programación en línea y definitivamente no puedo entender cómo piensa la gente de la lógica de los aspectos de esta. Yo creo que está vinculada a la tabla de verdad de la siguiente, que muestra a través de la división de los casos que los valores pueden ser cambiados.

Sin embargo, estoy seguro de que el pleno de razonamiento de por qué esto funciona, como si hay alguna teoremas matemáticos que debo saber que me puede ayudar en mi entendimiento.

PS: lo Siento si la pregunta es off-topic aquí, se siente como una programación de la pregunta, pero tengo la sensación de que estoy más preocupado por la "lógica" en lugar de la programación. También me llamó la tabla de mí mismo en MS word, ya que no puede obtener el látex para trabajar de alguna manera.

Answer 1

Tenga en cuenta que puede hacer lo mismo sin operadores bit a bit (al menos para tipos enteros sin signo, ya que no pueden desbordarse en un comportamiento indefinido):

         // i == x     j == y
i += j; // i == x+y   j == y
j -= i; // i == x+y   j == -x
i += j; // i == y     j == -x
j = -j; // i == y     j == x
 

Ahora bien, si hacemos este bit por bit , pero módulo 2 en vez de módulo UINT_MAX+1 , la operación XOR implementa suma y resta, y la negación final es no operativa porque$-1\equiv 1$ y$-0\equiv 0 \pmod 2$. Entonces, lo que queda en la versión bit a bit es exactamente

 i ^= j; j ^= i; i ^= j;
 

Answer 2

En términos algebraicos, el operador XOR (o$\oplus$) no es más que módulo de adición$2$: use$1$ y$0$ para verdadero y falso , junto con$1 \oplus 1 = 0$

Ahora, dado que el módulo adicional$2$ es asociativo y conmutativo , y ambos elementos son sus propios inversos, tenemos $$ \begin{align} d &= b \oplus c\\ &= b \oplus (a \oplus b)\\ &= b \oplus (b \oplus a)\\ &= (b \oplus b) \oplus a\\ &= a.\\ \end {align} $$

Podemos mostrar$e = b$ con un razonamiento similar.

Answer 3

Ya respondió su pregunta, pero si desea una explicación algebraica, tenga en cuenta que para cualquier$x$:

ps

ps

Asi que:

ps

ps

ps

ps