Zig Zag Расшифровка

Question

В буферах протокола Google обзор кодировки они вводят что-то, называемое "Zig Zag Encoding", это берет числа со знаком, которые имеют небольшую величину, и создает ряд чисел без знака, которые имеют небольшую величину .

Например

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-разрядные целые числа со знаком

Answer 1

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

(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

Answer 2

Вот еще один способ сделать то же самое, только для пояснения (очевидно, вы должны использовать однострочник 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;
}

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

Answer 3

Как насчет

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

Answer 4

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

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

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

Answer 5

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

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

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

Answer 6

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

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]