Zig Zag Dekodowanie

Question

W buforach protokołu google encoding overview, wprowadzają one coś, co nazywa się "Kodowaniem Zig Zag", to bierze podpisane liczby, które mają niewielką wielkość i tworzy serię liczb bez znaku, które mają niewielką wielkość.

Na przykład

Encoded => Plain 
0 => 0 
1 => -1 
2 => 1 
3 => -2 
4 => 2 
5 => -3 
6 => 3 

i tak dalej. Funkcja kodowania dają za to jest dość sprytny, to:

(n << 1)^(n >> 31) //for a 32 bit integer 

rozumiem jak to działa, jednak nie mogę dla życia mnie dowiedzieć się, jak odwrócić ten i dekoduje go z powrotem do podpisanych 32 bitowych liczb całkowitych

Answer 1

Spróbuj tego:

(n >> 1)^(-(n & 1)) 

Edit:

jestem delegowania przykładowy kod weryfikacji:

#include <stdio.h> 

int main() 
{ 
    unsigned int n; 
    int r; 

    for(n = 0; n < 10; n++) { 
    r = (n >> 1)^(-(n & 1)); 
    printf("%u => %d\n", n, r); 
    } 

    return 0; 
} 

uzyskać następujące wyniki:

0 => 0 
1 => -1 
2 => 1 
3 => -2 
4 => 2 
5 => -3 
6 => 3 
7 => -4 
8 => 4 
9 => -5 

Answer 2

znalazłem rozwiązanie, niestety nie jest to piękno jedna linia miałem nadzieję:

uint signMask = u << 31; 
int iSign = *((Int32*)&signMask); 
iSign >>= 31; 
signMask = *((UInt32*)&iSign); 

UInt32 a = (u >> 1)^signMask; 
return *((Int32*)&a); 

Answer 3

Jestem pewien, że istnieje jakiś super-wydajne operacje bitowe, które to zrobić szybciej, ale funkcja ta jest prosta . Oto implementacja Pythona:

def decode(n): 
    if (n < 0): 
    return (2 * abs(n)) - 1 
    else: 
    return 2 * n 

>>> [decode(n) for n in [0,-1,1,-2,2,-3,3,-4,4]] 
[0, 1, 2, 3, 4, 5, 6, 7, 8] 

Answer 4

Jak o

(n>>1) - (n&1)*n 

Answer 5

Oto kolejny sposób robi to samo, tylko w celach wyjaśniających (należy oczywiście użyć jednego-liner 3lectrologos').

Po prostu musisz zauważyć, że masz xor z liczbą, która jest albo całością 1 (równoznaczna z bitową nie), albo liczbą zero (równoważną nie robieniem niczego). To daje (-(n & 1)), lub to, co wyjaśnia wyjaśnienie Google "arytmetyczna zmiana".

int zigzag_to_signed(unsigned int zigzag) 
{ 
    int abs = (int) (zigzag >> 1); 

    if(zigzag % 2) 
     return ~abs; 
    else 
     return abs; 
} 

unsigned int signed_to_zigzag(int signed) 
{ 
    unsigned int abs = (unsigned int) signed << 1; 

    if(signed < 0) 
     return ~abs; 
    else 
     return abs; 
} 

Aby więc mieć dużo 0 jest na najważniejszych stanowiskach, kodowanie zygzak wykorzystuje LSB jako bit znaku oraz pozostałych bitów jako wartość bezwzględną (tylko dla dodatnich liczb całkowitych faktycznie i wartości bezwzględnej -1 dla liczb ujemnych z powodu reprezentacji uzupełnienia 2).

Answer 6

Po zabawie z zaakceptowaną odpowiedzią zaproponowaną przez 3lectrologos, nie mogłem jej uruchomić, gdy zaczynałem od unsigned longs (w C# - błąd kompilatora). I wymyślił coś podobnego Zamiast:

(value >> 1)^(~(value & 1) + 1) 

Działa to doskonale dla każdego języka, który reprezentuje liczb ujemnych w 2 za komplement (np NET).