В буферах протокола 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-битные целые числа
Попробуйте следующее:
(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
Как насчет
(n>>1) - (n&1)*n
Вот еще один способ сделать то же самое, просто для объяснения целей (вы должны, очевидно, использовать однострочный слой 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 дополняющих представлений).
Я нашел решение, к сожалению, это не единственная красота, на которую я надеялся:
uint signMask = u << 31;
int iSign = *((Int32*)&signMask);
iSign >>= 31;
signMask = *((UInt32*)&iSign);
UInt32 a = (u >> 1) ^ signMask;
return *((Int32*)&a);
После того, как вы согласились с принятым ответом, предложенным 3lectrologos, я не смог заставить его работать, когда начинался с unsigned longs (в С# - ошибка компилятора). Вместо этого я придумал нечто похожее:
( value >> 1 ) ^ ( ~( value & 1 ) + 1 )
Это отлично подходит для любого языка, который представляет отрицательные числа в 2 комплиментах (например,.NET).
Я уверен, что есть некоторые суперэффективные побитовые операции, которые делают это быстрее, но функция проста. Здесь реализована реализация 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]