Декодирование Zig Zag

В буферах протокола google encoding overview они вводят что-то, называемое «Zig Zag Encoding», это принимает подписанные числа с небольшой величиной и создает серию беззнаковых чисел, которые имеют малую величину.Декодирование Zig Zag

Например

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

И так далее. Функция кодирования они дают для этого достаточно умна, это:

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

Я понимаю, как это работает, однако, я не могу за жизнь мне понять, как изменить это и декодировать его обратно в подписанных 32-разрядных целых чисел

источник

2010-02-05 Martin

Попробуйте это:

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

Edit:

Я отправляю некоторые примеры кода для проверки:

#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; 
}

Я получаю следующие результаты:

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

источник

2010-02-05 23:03:39 3lectrologos

Я знал, что должен быть способ размножения. Престижность! – ergosys

Этот, похоже, не работает:/ – Martin

Ну, это работает для меня и для ergosys, поэтому он тоже должен работать для вас ... Можете ли вы рассказать мне, какие результаты вы получите? – 3lectrologos

Я нашел решение, к сожалению, это не одна линия красоты я надеялся:

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

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

источник

2010-02-05 22:45:02 Martin

-1

Я уверен, что есть некоторые супер-эффективные битовые операции, которые делают это быстрее, но функция проста , Вот реализация питон:

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]

источник

2010-02-05 22:45:43 aem

Спасибо, но, к сожалению, это в сетевой системе кодирования для игры, и эта функция декодирования используется много раз для каждого пакета, много раз в секунду - это должно быть _fast_ – Martin

Вы можете использовать простой бит op для ускорения этого немного. Сдвиг на 1 для умножения на 2. –

-1: Эта функция * кодирует * подписанные числа в кодированные неподписанные числа. В исходном вопросе уже есть функция, которая делает это. В исходном вопросе была задана функция, которая * декодирует * эти неподписанные числа обратно к исходным подписанным числам: мы хотим, чтобы декодировать (3), чтобы вернуть -2, но эта функция делает decode (3) return 6. –

Как насчет

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

источник

2010-02-05 22:49:23 ergosys

ну, это работает, но как ? – Martin

n четное: n/2 n нечетное: n/2 - n – ergosys

huh, это довольно аккуратно – Martin

Вот еще один способ сделать то же самое, только в иллюстративных целях (вы должны явно использовать один вкладыш 3lectrologos').

Вы просто должны заметить, что вы xor с числом, которое равно либо 1 (эквивалентно побитовому), либо всем 0 (что равносильно тому, чтобы ничего не делать). Вот что дает (-(n & 1)) или что объясняется замечанием «арифметического сдвига» Google.

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; 
}

Так что для того, чтобы иметь много 0 на наиболее важных положениях, зигзаг кодирование использует LSB в качестве знакового бита, и другие биты, как абсолютное значение (только для положительных целых чисел собственно, и абсолютное значение -1 для отрицательных чисел из-за представления дополнения 2).

источник

2012-09-21 22:31:07 Cimbali

'zigZag_to_signed' не возвращает исходное значение. – Salar

@SalarKhalilzadeh Спасибо, исправлено. Оператор предшествует nce был неправильным, кастинг, а затем смещение потеряло первый бит «зигзага». – Cimbali

После прошивки с принятым ответом, предложенным 3lectrologos, я не мог заставить его работать, начиная с unsigned longs (в C# - ошибка компилятора). Я придумал нечто подобное вместо:

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

Это прекрасно работает для любого языка, который представляет отрицательные числа в 2-х в комплимента (например, .NET).

источник

2013-10-30 15:43:43 Imisnew2

ответ

Смежные вопросы