Буферы протокола Google: кодирование зигзага

Question

Из «подписанных типов» на Кодирование - буферы протокола - код Google:

Зигзагские кодирующие карты подписали целые числа для не знаковых целых чисел, так что числа с небольшим абсолютным значением (например, -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) быть 1111 1110? (Бит на негативы хорошо сформировано на любом языке?)

Тем не менее, используя Fomula и выполнение (-1 << 1) ^ (-1 >> 31), предполагая 32-битный int, я получаю 1111 1111, который составляет 4 миллиарда, тогда как таблица считает, что у меня должен быть 1.

Answer 1

Смещение отрицательного подписанного целого числа вправо копии знак, так что это

(-1 >> 31) == -1

Затем,

(-1 << 1) ^ (-1 >> 31) = -2 ^ -1
                       = 1

Это может быть легче визуализировать в двоичном (8 бит здесь):

(-1 << 1) ^ (-1 >> 7) = 11111110 ^ 11111111
                      = 00000001

Answer 2

Другой способ подумать о картировании Zig Zag - это то, что это небольшой поворот на знаке и магнитуде.

В картировании Zig ZAG наименее значимый бит (LSB) отображения указывает на знак значения: если это 0, то исходное значение неотрицательное, если оно 1, то исходное значение отрицательное.

Незначальные значения просто оставляются на один бит, чтобы освободить место для бита знака в LSB.

Для отрицательных значений вы можете сделать тот же самый бит левого сдвига для абсолютного значения (величины) числа и просто попросить LSB указать знак. Например, -1 может сопоставить до 0x03 или 0B00000011, где LSB указывает, что он отрицательный, а величина 1 остается сдвинутой на 1 бит.

Уродливая вещь об этом знаке и представлении величины - «отрицательный нулевой», нанесенный на карту 0x01 или 0B00000001. Этот вариант нуля «использует» одно из наших значений и сдвигает диапазон целых чисел, который мы можем представлять одним. Мы, вероятно, хотим, чтобы карта специального случая отрицательно от -2^63, чтобы мы могли представлять полный диапазон комплемента 64B 2 [-2^63, 2^63). Это означает, что мы использовали одну из наших ценных единичных кодировки для представления значения, которое будет очень, очень, очень редко использоваться в кодировании, оптимизированном для малых величин, и мы представили особый случай, что плохо.

Именно здесь происходит поворот Зиг Зага на этом знаке и знаке. Бит знака все еще находится в LSB, но для отрицательных чисел мы вычитаем его из величины, а не специального отрицательного нуля. Теперь -1 карты до 0x01 и -2^63 также имеют неспециальное представление случая (т.е. величина 2^63 -1, влево сдвинуло один бит, с набором битов LSB / знака, который представляет собой биты, установленные на 1s) Анкет

Таким образом, еще один способ подумать о кодировании Зиг Заг - это то, что это более умное знаком и представление величины: бит знака хранится в LSB, 1 вычитается из величины отрицательных чисел, а величина остается сдвинутой на один бит.

Быть быстрее реализовать эти преобразования, используя безусловные битовые операторы, которые вы разместили, а не явно тестируя знак, манипулируя негативными значениями специального случая (например, отрицают и вычитайте 1 или по биту), сдвигают величину, а затем явные настройки Знак LSB. Тем не менее, они эквивалентны в действии, и этот более явный знака и серия шагов величины может быть легче понять, что и почему мы делаем эти вещи.

Я предупреждаю вас, хотя эти отрицательные значения в C / C ++ не переносимы и следует избегать. Левое смещение отрицательного значения имеет неопределенное поведение, а правое изменение отрицательного значения имеет определяющее поведение. Даже оставшееся смещение положительного целого числа может иметь неопределенное поведение (например, если вы перейдете в бит знака, это может вызвать ловушку или что -то хуже). Так что, в целом, не бить подписанные типы подписания в C / C ++. "Просто сказать нет."

Сначала выставьте незначенную версию типа, чтобы получить безопасные, четко определенные результаты в соответствии со стандартом. Это означает, что у вас не будет арифметического смещения отрицательных значений - только логический сдвиг, поэтому вам необходимо настроить логику для учета этого.

Вот безопасные и портативные версии отображений Zig ZAG для 64B целых чисел в C (обратите внимание на арифметическое отрицание):

#include <stdint.h>

uint64_t zz_map( int64_t x )
{
  return ( ( uint64_t ) x << 1 ) ^ -( ( uint64_t ) x >> 63 );
}

int64_t zz_unmap( uint64_t y )
{
  return ( int64_t ) ( ( y >> 1 ) ^ -( y & 0x1 ) );
}

Answer 3

Позвольте мне добавить два цента в обсуждение. Как отмечались другие ответы, кодирование зигзагообразного ZAG можно рассматривать как поворот знака. Этот факт может быть использован для реализации функций преобразования, которые работают для целых чисел произвольного размера. Например, я использую следующий код в одном в своих проектах Python:

def zigzag(x: int) -> int:
    return x << 1 if x >= 0 else (-x - 1) << 1 | 1

def zagzig(x: int) -> int:
    assert x >= 0
    sign = x & 1
    return -(x >> 1) - 1 if sign else x >> 1

Эти функции работают, несмотря на Python int не имеет фиксированной битовой провайды; Вместо этого он расширяется динамически. Однако этот подход может быть неэффективным в скомпилированных языках, поскольку он требует условного ветвления.