Qual'è la funzione inversa di x XOR (x/2)?

Question

Che cosa è la funzione inversa di x XOR (x/2)?

Esiste un sistema di regole per la risoluzione delle equazioni, simile all'algebra, ma con operatori logici?

Answer 1

Supponiamo di avere un numero x di N bit. Si potrebbe scrivere questo come:

b(N-1) b(N-2) b(N-3) ... b(0) 

dove b(i) è il numero di bit i nel numero (dove 0 è il bit meno significativo).

x/2 è lo stesso di x spostato a sinistra di 1 bit. Assumiamo numeri non firmati. Quindi:

x/2 = 0 b(N-1) b(N-2) ... b(1) 

Ora abbiamo XOR x con x/2:

x^(x/2) = b(N-1)^0 b(N-2)^b(N-1) b(N-3)^b(N-2) ... b(0)^b(1) 

Si noti che il bit più a destra (il bit più significativo) di questo è che è b(N-1)^0b(N-1). In altre parole, è possibile ottenere immediatamente il bit b(N-1) dal risultato. Quando hai questo bit, puoi calcolare b(N-2) perché il secondo bit del risultato è b(N-2)^b(N-1) e sai già b(N-1). E così via, è possibile calcolare tutti i bit b(N-1) a b(0) del numero originale x.

Answer 2

ti posso dare un algoritmo in bit:

Supponendo di avere un array di n bit:

b = [b1 .. bn] // b1-bn are 0 or 1 

La matrice originale è:

x0 = b0 
x1 = b1^x0 
x2 = b2^x1 

o in generale

x[i] = b[i]^x[i-1] 

Answer 3

Assum e Y = X^(X/2)

Se si vuole trovare X, fare questo

X = 0 

do 

    X ^= Y 
    Y /= 2 

while Y != 0 

Spero che aiuta!

Answer 4

So che è un argomento vecchio, ma mi sono imbattuto nella stessa domanda, e ho scoperto un piccolo trucco. Se si dispone n bit, invece di richiedere n bit operazioni (come la risposta di Jesper), è possibile farlo con log2 (n) numero operazioni:

Supponiamo che y sia pari a x XOR (x/2) all'inizio del programma, si può fare il seguente programma C:

INPUT : y 

int i, x; 
x = y; 
for (i = 1; i < n; i <<= 1) 
    x ^= x >> i; 

OUTPUT : x 

e qui si ha la soluzione.

• ">>" è l'operazione di spostamento bit corretta. Ad esempio il numero 13, 1101 in binario, se spostato di 1 a destra, diventerà 110 in binario, quindi 13 >> 1 = 6. x >> i è equivalente a x/2^i (divisione negli interi, ovviamente)
• "< <" è l'operazione di spostamento a sinistra bit (i < < = 1 è equivalente a i * = 2)

Perché funziona? Prendiamo come esempio n = 5 bit, e iniziano con y = b4 b3 b2 b1 b0 (in binario: nella seguente x è scritto in binario anche, ma è scritto in decimale)

• inizializzazione:

x = b4 b3 b2 b1 b0

• primo passo: i = 1

x >> 1 = b4 b3 b2 b1 quindi abbiamo x = b4 b3 b2 b1 b0 XOR b3 b2 b1 b0 = b4 (b3^b4) (b2^b3) (b1^b2) (b0^b1)

• Secondo passo: i = 2

x >> 2 = b4 (b3^b4) (b2^b3) quindi abbiamo x = b4 (b3^b4) (b2^b3) (b1^b2) (b0^b1) XOR b4 (b3^b4) (b2^b3) = b4 (b3^b4) (b2^b3^b4) (b1^b2^b3^b4) (b0^b1^b2^b3)

• Terzo passo: i = 4

x >> 4 = b4 quindi abbiamo x = b4 (b3^b4) (b2^b3^b4) (b1^b2^b3^b4) (b0^b1^b2^b3) XOR b4 = b4 (b3^b4) (b2^b3^b4) (b1^b2^b3^b4) (b0^b1^b2^b3^b4)

• Poi i = 8, che è più di 5, si esce dal ciclo continuo.

E abbiamo l'output desiderato.

Il ciclo ha iterazioni log2 (n) perché inizio a 1 e viene moltiplicato per 2 ad ogni passaggio, quindi per i n raggiungere, dobbiamo farlo log2 (n) volte.