Google Protocol Buffer: ZigZag Codifica

Question

Da "Tipi firmato" sul di codifica - buffer protocollo - Google Code :

zigzag codifica alle mappe interi firmato interi senza segno modo che i numeri con un piccolo valore assoluto (ad esempio, -1) hanno un piccolo valore varint codificato troppo. Si fa in modo che "zig-zag" avanti e indietro attraverso i numeri interi positivi e negativi, cosicché -1 viene codificato come 1, 1 è codificato come 2, -2 viene codificato come 3, e così via, come si può vedere nella tabella che segue:

Signed Original  Encoded As
0                0
-1               1
1                2
-2               3
2147483647       4294967294
-2147483648      4294967295

In altre parole, ogni valore n è codificato utilizzando

(n << 1) ^ (n >> 31)

per sint32s, o

(n << 1) ^ (n >> 63)

per la versione a 64 bit.

Come funziona (n << 1) ^ (n >> 31) cosa uguali nella tabella? Capisco che avrebbe funzionato per i positivi, ma come funziona per dire, -1? Non sarebbe -1 essere 1111 1111, e (n << 1) essere 1111 1110? (Is bit-shifting sul negativi ben formati in qualsiasi lingua?)

Tuttavia, utilizzando la fomula e facendo (-1 << 1) ^ (-1 >> 31), ipotizzando un 32 bit int, ottengo 1111 1111, che è di 4 miliardi di dollari, mentre il tavolo pensa che dovrei avere 1.

Answer 1

Lo spostamento di un intero negativo firmato a destra copie il bit di segno, in modo che

(-1 >> 31) == -1

Poi,

(-1 << 1) ^ (-1 >> 31) = -2 ^ -1
                       = 1

Questo potrebbe essere più facile da visualizzare in binario (8 bit qui):

(-1 << 1) ^ (-1 >> 7) = 11111110 ^ 11111111
                      = 00000001

Answer 2

Un altro modo di pensare a zig zag mappatura è che si tratta di una leggera torsione su una rappresentazione segno e grandezza.

In zig zag mappatura, il bit meno significativo (LSB) della mappatura indica il segno del valore: se è 0, quindi il valore originale è non negativo, se è 1, allora il valore originale è negativo.

I valori non negativi sono semplicemente lasciati spostato di un bit a fare spazio per il bit del segno in LSB.

Per valori negativi, si potrebbe fare lo stesso un bit spostamento a sinistra per il valore assoluto (magnitudo) del numero e semplicemente hanno LSB indicare il segno. Ad esempio, -1 potrebbe mappare a 0x03 o 0b00000011, dove LSB indica che è negativo e la grandezza di 1 viene lasciato spostato di 1 bit.

La cosa brutta di questo segno e la grandezza rappresentazione è "negativo pari a zero," mappata come 0x01 o 0b00000001. Questa variante di zero "consuma" uno dei nostri valori e sposta l'intervallo di numeri interi che può rappresentare per uno. Probabilmente vogliamo caso speciale mappa zero negativo a -2 ^ 63, in modo da poter rappresentare la gamma completa 64b 2 del complemento [-2 ^ 63, 2 ^ 63). Ciò significa che abbiamo usato uno dei nostri preziosi codifiche singolo byte per rappresentare un valore che sarà molto, molto, molto raramente essere utilizzato in una codifica ottimizzato per i numeri piccoli di grandezza e che abbiamo introdotto un caso speciale, che è male.

Questo è dove svolta a zig zag di questo segno e la grandezza di rappresentanza accade. Il bit di segno è ancora in lsb, ma per i numeri negativi, abbiamo sottrarre uno dalla grandezza piuttosto che speciale involucro negativo pari a zero. Ora, -1 mappe di 0x01 e -2 ^ 63 ha una rappresentazione non-speciale caso troppo (vale a dire - magnitudo 2 ^ 63-1, sinistra spostato un po ', con LSB / sign set bit, che è tutti i bit impostati a 1s) .

Quindi, un altro modo di pensare a zig zag codifica è che si tratta di un segno e la grandezza di rappresentanza più intelligente: il bit del segno è memorizzato in LSB, 1 viene sottratto dalla grandezza dei numeri negativi, e la grandezza è lasciato spostato uno bit.

E 'più veloce da implementare queste trasformazioni utilizzando gli operatori bit per bit incondizionate che hai postato, piuttosto che test esplicitamente il segno, i valori negativi la manipolazione di casi particolari (ad esempio - negate e sottrarre 1, o NOT bit a bit), spostando la grandezza, e quindi impostando esplicitamente LSB bit di segno. Tuttavia, essi sono equivalenti a tutti gli effetti e questo segno e la grandezza più esplicita serie di passi potrebbe essere più facile da capire che cosa e perché stiamo facendo queste cose.

I vi avvertirà se quel po 'spostando i valori negativi in ??C / C ++ non è portabile e dovrebbe essere evitato. Sinistra spostando un valore negativo ha un comportamento indefinito e destra spostando un valore negativo ha comportamento attuazione definito. Anche a sinistra spostando un intero positivo può avere un comportamento indefinito (per esempio - se si sposta nel segno bit potrebbe causare una trappola o qualcosa di peggio). Quindi, in generale, non si po 'spostare i tipi firmati in C / C ++. "Dì semplicemente di no."

Cast prima alla versione senza segno del tipo di avere risultati sicuri e ben definiti secondo lo standard. Questo vuol dire che poi non avrete spostamento aritmetica dei valori negativi -. Solo turno di logica, quindi è necessario regolare la logica per conto che

Ecco le versioni sicuro e portatile del zig zag mappature per gli interi 64b in C (nota la negazione aritmetica):

#include <stdint.h>

uint64_t zz_map( int64_t x )
{
  return ( ( uint64_t ) x << 1 ) ^ -( ( uint64_t ) x >> 63 );
}

int64_t zz_unmap( uint64_t y )
{
  return ( int64_t ) ( ( y >> 1 ) ^ -( y & 0x1 ) );
}

Answer 3

Mi permetto di aggiungere i miei due centesimi alla discussione. Come hanno notato anche altre risposte, lo zig-zag codifica può essere pensato come una torsione segno di magnitudo. Questo fatto può essere utilizzato per implementare funzioni di conversione che lavorano per interi arbitrari dimensioni. Ad esempio, io uso il seguente codice in un solo sui miei progetti Python:

def zigzag(x: int) -> int:
    return x << 1 if x >= 0 else (-x - 1) << 1 | 1

def zagzig(x: int) -> int:
    assert x >= 0
    sign = x & 1
    return -(x >> 1) - 1 if sign else x >> 1

Queste funzioni nonostante int di Python non ha fissa bitwidth; invece, si estende dinamicamente. Tuttavia, questo approccio può essere inefficiente in linguaggi compilati in quanto richiede ramificazione condizionale.