От "Подписанные типы" на Кодирование - Буферы протокола - Код 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.
Смещение отрицательного целого числа со знаком вправо копирует бит знака, так что
(-1 >> 31) == -1
Затем
(-1 << 1) ^ (-1 >> 31) = -2 ^ -1
= 1
Это может быть проще визуализировать в двоичном формате (8 бит здесь):
(-1 << 1) ^ (-1 >> 7) = 11111110 ^ 11111111
= 00000001