Como é que XOR variável trocando trabalho?

Question

Alguém pode me explicar como XOR trocando de duas variáveis ??sem obras variável TEMP?

void xorSwap (int *x, int *y)
{
    if (x != y) {
        *x ^= *y;
        *y ^= *x;
        *x ^= *y;
    }
}

Eu entendo o que ele faz, mas alguém pode me percorrer a lógica de como ele funciona?

Answer 1

Você pode ver como ele funciona, fazendo a substituição:

x1 = x0 xor y0
y2 = x1 xor y0
x2 = x1 xor y2

Substituindo,

x1 = x0 xor y0
y2 = (x0 xor y0) xor y0
x2 = (x0 xor y0) xor ((x0 xor y0) xor y0)

Porque xor é totalmente associativo e comutativo:

y2 = x0 xor (y0 xor y0)
x2 = (x0 xor x0) xor (y0 xor y0) xor y0

Desde x xor x == 0 para qualquer x,

y2 = x0 xor 0
x2 = 0 xor 0 xor y0

E desde x xor 0 == x para qualquer x,

y2 = x0
x2 = y0

E o swap é feito.

Answer 2

Outras pessoas têm explicou ele, agora eu quero explicar por que era uma boa idéia, mas agora não é.

De volta ao dia quando tivemos simples de ciclo simples ou multi-ciclo CPUs, era mais barato para usar esse truque para evitar dereferences memória caros ou registros derramando para a pilha. No entanto, agora temos CPUs com tubulações enormes vez. gasoduto do P4 variou de ter etapas de 20 a 31 (ou mais) em seus dutos, onde qualquer dependência entre ler e escrever para um registo poderiam causar a coisa toda para stall. O swap xor tem algumas dependências muito pesados ??entre A e B que realmente não importa a todos, mas parar o oleoduto na prática. Um gasoduto parado provoca um caminho de código lento, e se este swap está em seu circuito interno, você vai estar se movendo muito lentamente.

Na prática geral, o seu compilador pode descobrir o que você realmente quer fazer quando você fazer uma troca com uma variável temporária e pode compilá-lo para uma única instrução XCHG. Usando a troca xor torna muito mais difícil para o compilador para adivinhar sua intenção e, portanto, muito menos propensos a otimizá-lo corretamente. para não mencionar a manutenção do código, etc.

Answer 3

Eu gosto de pensar nisso graficamente em vez de numericamente.

Digamos que você começar com x = 11 e y = 5 Em binário (e eu vou usar uma máquina de 4 bits hipotético), aqui está x e y

       x: |1|0|1|1|   -> 8 + 2 + 1
       y: |0|1|0|1|   -> 4 + 1

Agora, para mim, XOR é uma operação invertido e fazê-lo duas vezes é um espelho:

     x^y: |1|1|1|0|
 (x^y)^y: |1|0|1|1|   <- ooh!  Check it out - x came back
 (x^y)^x: |0|1|0|1|   <- ooh!  y came back too!

Answer 4

Aqui está um que deve ser um pouco mais fácil de Grokar:

int x = 10, y = 7;

y = x + y; //x = 10, y = 17
x = y - x; //x = 7, y = 17
y = y - x; //x = 7, y = 10

Agora, pode-se entender a XOR enganar um pouco mais facilmente através da compreensão de que ^ pode ser pensado como + ou - . Assim como:

x + y - ((x + y) - x) == x 

, assim:

x ^ y ^ ((x ^ y) ^ x) == x

Answer 5

A razão pela qual ele funciona é porque XOR não informações perder. Você poderia fazer a mesma coisa com a adição ordinária e subtração se podia ignorar estouro. Por exemplo, se a variável par A, B originalmente contém os valores de 1,2, você pode trocá-los como este:

 // A,B  = 1,2
A = A+B // 3,2
B = A-B // 3,1
A = A-B // 2,1

BTW há um velho truque para codificar uma lista ligada 2-way em um "ponteiro" single. Suponha que você tenha uma lista de blocos de memória em endereços A, B e C. A primeira palavra em cada bloco é, respectivamente:

 // first word of each block is sum of addresses of prior and next block
 0 + &B   // first word of block A
&A + &C   // first word of block B
&B + 0    // first word of block C

Se você tiver acesso ao bloco A, que lhe dá o endereço do B. Para chegar a C, você pega o "ponteiro" em B e subtrair A, e assim por diante. Ele funciona tão bem para trás. Para executar ao longo da lista, você precisa manter ponteiros para dois blocos consecutivos. Claro que você usaria XOR no lugar de adição / subtração, para que você não precisa se preocupar em excesso.

Você poderia estender isso para uma "teia ligada" se você quiser ter algum divertimento.

Answer 6

A maioria das pessoas iria trocar duas variáveis ??x e y usando uma variável temporária, como este:

tmp = x
x = y
y = tmp

Aqui está um truque de programação arrumado para trocar dois valores sem a necessidade de um temp:

x = x xor y
y = x xor y
x = x xor y

Mais detalhes no swap duas variáveis ??usando XOR

Na linha 1 combinamos x e y (usando XOR) para obter este “híbrido” e armazená-lo de volta em x. XOR é uma ótima maneira de salvar as informações, porque você pode removê-lo fazendo um XOR novamente.

Na linha 2. Nós XOR o híbrido com y, que anula todas as informações y, deixando-nos apenas com x. Nós salvar este resultado volta para y, então agora eles têm trocado.

Na última linha, X ainda tem o valor híbrido. Nós XOR-lo mais uma vez com y (agora com valor original de x) para remover todos os vestígios de x fora do híbrido. Isso nos deixa com y, e a troca é completa!

---

O computador realmente tem uma variável implícito “temp” que os resultados lojas intermediários antes de escrever-los de volta a um registo. Por exemplo, se você adicionar 3 a um registo (em pseudocódigo de linguagem de máquina):

ADD 3 A // add 3 to register A

A ALU (Arithmetic Logic Unit) é realmente o que executa a instrução 3 + A. Leva as entradas (3, a) e cria um resultado (3 + A), que a CPU em seguida, armazena cópias em registro original de A. Então, usamos a ALU como espaço de rascunho temporário antes tivemos a resposta final.

Tomamos dados temporários implícitas da ALU para concedido, mas é sempre lá. De forma semelhante, a ALU pode devolver o resultado intermediário do XOR no caso de x = x xor y, altura em que a CPU armazena ele no registro original de x.

Porque não estamos acostumados a pensar sobre os pobres, negligenciadas ALU, o swap XOR parece mágico porque ele não tem uma variável temporária explícito. Algumas máquinas têm um 1-passo instrução troca XCHG para trocar dois registros.

Answer 7

@VonC tem direito, é um truque matemático puro . Imagine-4 palavras pouco e ver se isso ajuda.

word1 ^= word2;
word2 ^= word1;
word1 ^= word2;


word1    word2
0101     1111
after 1st xor
1010     1111
after 2nd xor
1010     0101
after 3rd xor
1111     0101

Answer 8

Basicamente, existem 3 passos na abordagem XOR:

a’= a XOR b (1)
b’= um’ b XOR (2)
um”= um’ XOR b’(3)

Para entender por isso funciona primeira nota que:

1. XOR irá produzir um 1 apenas se exatamente um de seus operandos é 1, eo outro é zero;
2. XOR é conmutativo assim um XOR b = b XOR um;
3. XOR é associativo de modo (uma XOR b) XOR c = um OU-EXCLUSIVO (XOR b c); e
4. a XOR a = 0 (isto deve ser óbvio a partir da definição na 1 acima)

depois do passo (1), a representação binária de uma terá 1-bits única nas posições de bits em que a e b possuem os bits opostos. Que é ou (k = 1, bk = 0) ou (AK = 0, bk = 1). Agora, quando fazemos a substituição no Passo (2) obtemos:

b’= (a XOR b) XOR b
= Um OU-EXCLUSIVO (XOR b b) porque XOR é associativo
= Um XOR 0 por causa da [4] acima
= A, devido à definição de XOR (ver 1 acima)

Agora podemos substituir em Passo (3):

a”= (a XOR b) XOR um
= (B XOR a) XOR uma porque XOR é conmutativo
= B XOR (um XOR um) porque XOR é associativo
= B XOR 0 por causa da [4] acima
= B devido à definição de OU-EXCLUSIVO (ver 1 acima)

Informações mais detalhadas aqui: necessária e suficiente

Answer 9

Como uma nota lateral eu reinventou esta roda de forma independente há vários anos na forma de troca de números inteiros fazendo:

a = a + b
b = a - b ( = a + b - b once expanded)
a = a - b ( = a + b - a once expanded).

(Isto é mencionado acima, em um difícil de ler way),

O mesmo raciocínio se aplica a exata swaps XOR: a ^ b ^ b = a e a ^ b ^ a = a. Desde xor é comutativa, x ^ x = 0 e x ^ 0 = x, isso é muito fácil ver desde

= a ^ b ^ b
= a ^ 0
= a

e

= a ^ b ^ a 
= a ^ a ^ b 
= 0 ^ b 
= b

Espero que isso ajude. Esta explicação já foi dada ... mas não muito claramente imo.