Зачем менять местами байты в кодировке переменной длины в Thrift CompactProtocol?

Question

Мне было интересно, почему вам пришлось менять местами байты в Trift CompactProtocol при кодировании Ints с переменной длиной.

Пример взят из Приложения с интенсивным использованием данных (онлайн, стр. 120):

Number in Base 10 to be encoded: 1337
1337 in Base 2: 0010100 111001
Encoding first byte:  1|111011|0
Encoding second byte: 0|0010100

Как вы видите, байты были поменяны местами.Почему это так?

Дополнительная информация: Первый бит в первом байте означает, что впереди еще один байт.Последний бит в первом байте представляет знак (в данном случае положительный).Первый бит в последнем знаке означает, что больше нет байтов, принадлежащих этому номеру.

Answer 1

Это эффективный способ кодирования маленьких целых чисел, или, точнее, маленьких абсолютных значений.Идея объяснена в документации protobuf очень хорошо:

Кодировка ZigZag отображает целые числа со знаком в целые числа без знака, так что числа с небольшим абсолютным значением (например, -1) имеютмаленькое значение в кодировке varint тоже.Он делает это таким образом, что «зигзаги» взад и вперед через положительные и отрицательные целые числа, так что -1 кодируется как 1, 1 кодируется как 2, -2 кодируется как 3, и так далее, как высм. в следующей таблице [...]

Небольшие абсолютные значения - очень распространенный случай. Большие значения встречаются довольно редко.Следовательно, для большинства случаев использования мы будем иметь много (ненужных) нулей без добавленной стоимости.К сожалению, для отрицательных значений это немного сложнее, потому что мы должны заботиться о знаковом бите.

Алгоритм ZigZag заботится об этом очень элегантно и очень эффективно.