От "Подписанные типы" на Кодирование - Буферы протокола - Код Google:
ZigZag-кодирование отображает целые числа со знаком в целые числа без знака, так что числа с малым абсолютным значением (например, -1) также имеют небольшое переменное значение переменной. Он делает это таким образом, что "зигзаг" возвращается вперед и назад через положительные и отрицательные целые числа, так что -1 кодируется как 1, 1 кодируется как 2, -2 кодируется как 3 и так далее, поскольку вы можно увидеть в следующей таблице:
Signed Original Encoded As 0 0 -1 1 1 2 -2 3 2147483647 4294967294 -2147483648 4294967295
Другими словами, каждое значение n кодируется с использованием
(n << 1) ^ (n >> 31)
для sint32s или
(n << 1) ^ (n >> 63)
для 64-разрядной версии.
Как (n << 1) ^ (n >> 31)
равнозначно в таблице? Я понимаю, что это будет работать на позитивах, но как это работает, скажем, -1? Не было бы -1 1111 1111
, а (n << 1)
be 1111 1110
? (Является ли смещение бит по негативам хорошо сформированным на любом языке?)
Тем не менее, используя fomula и делая (-1 << 1) ^ (-1 >> 31)
, предполагая 32-битный int, я получаю 1111 1111
, что составляет 4 миллиарда, тогда как таблица считает, что у меня должно быть 1.