zigzag encodingとは - ちりもつもればミルキーウェイ

はじめに

符号付き整数は2の補数表現で表されることが多いが、エンコーディングによっては zigzag encoding なるものを使っている場合もある。

2の補数表現と比較した上で、zigzag encodingとはどういうバイト表現でどのような特徴があるかまとめる

みたほうがわかりやすいと思うのでとりあえず例

0b00000000: 0
0b00000001: -1
0b00000010: 1
0b00000011: -2
0b00000100: 2
~
0b01111111: -127
0b11111110: 127
0b11111111: -128

みれば丸わかりだけど、最下位bitを正負の判定bitにしちゃっている！というだけ
で、最下位bit以外の値を読んで負数だったら絶対値に+1したものを読み取る(+1してるのは2の補数表現と同じで0を正の数として扱ってるため)

2の補数表現は以下にざっとまとめをかいたので詳細はそちらを見てもらうとして

2の補数表現は大きく2つの以下の特徴がある

で、zigzag encoding はどういう特徴があるかというと

そのままでは演算できない(正負が交互に登場するし、かつ正の数はbitが立つほどプラス方向に大きくなるが、負数はbitが立つほどマイナス方向に大きくなるので、1つの数直線上に置くことができない)
負数の場合も絶対値が小さければあつかうbit数はすくない。-1なら下位1bitしか立たない

めちゃくちゃ対照的ですね。
こう見るとzigzag encodingは演算できないので取り回しがしづらそうですが、その分情報を表現するためのbit数が2の補数表現比で小さくできる場合がありそうです

これはズバリ可変長整数を取り扱うエンコーディングです

たとえば64bit符号付き可変長整数を扱うエンコーディングで -1 という値を表現するケースを考えてみます

2の補数表現をつかうと10byteの容量をつかいます！(各byteの先頭1bitは終端判定に使うと想定して)
なぜなら最上位1bitがたつので、64bitすべての情報を伝える必要があるからです

zigzag encodingをつかうと1byteですみます！
これはzigzag encodingは絶対値が小さい限り下位bitしか立たないため、伝えなければいけない情報が少なく済むためです

いいところ

わるいところ

つまり、zigzag encodingは 演算ができないことを許容できて、絶対値がちいさい負数が登場しうる 値に対してのみ利用するべきです。
そして、その効果は64bit可変長整数を使った場合、理想的なケースにおいて9byte近くエンコードされたバイト列の容量を削減できます！すごい！