Декодирование резкого поворота крутого поворота
В буферах протокола Google, кодирующих обзор, они представляют что-то позвонившее "Кодирование Резкого поворота Крутого поворота", это берет числа со знаком, которые имеют маленькую величину, и создает серию неподписанных чисел, которые имеют маленькую величину.
Например,
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 бита со знаком
4 ответа
Попробуйте это:
(n >> 1) ^ (-(n & 1))
Изменить:
Я отправляю образец кода для проверки:
#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
Я нашел решение, к сожалению, это не та единственная красота, на которую я надеялся:
uint signMask = u << 31;
int iSign = *((Int32*)&signMask);
iSign >>= 31;
signMask = *((UInt32*)&iSign);
UInt32 a = (u >> 1) ^ signMask;
return *((Int32*)&a);
I Я уверен, что есть несколько сверхэффективных побитовых операций, которые делают это быстрее, но функция проста. Вот реализация на 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]