zigzag壓縮算法

前文 Base 128 Varints 編碼（壓縮算法） 介紹了Base 128 Varints這種對數字傳輸的編碼，了解到了這種編碼方式是為了最大程度壓縮數字的。但是，在前文裡，我們隻談論到了正數的情況，那如果出現了負數，該怎麼辦？zigzag壓縮算法解決的就是這個問題。

在聊這個算法之前，我們得先補補課，聊聊二進制補碼相關的東東。

一、二進制及補碼

我們知道，計算機存儲的資料都是二進制的01串，而數字的01串又是以補碼的形式存儲的，補碼是什麼東西？為什麼要用補碼？下面我們一個個來看：

1.原碼

要了解補碼，首先要了解原碼。

什麼是原碼？簡單點說，就是把十進制轉為二進制的表示形式，我們用第一個位表示符号（0為非負數，1為負數），剩下的位表示值。比如：

[+8] = [00001000]原

[-8] = [10001000]原

2.反碼

我們用第一位表示符号（0為非負數，1為負數），剩下的位，非負數保持不變，負數按位求反。比如：

[+8] = [00001000]原 = [0000 1000]反

[-8] = [10001000]原 = [1111 0111]反

就是說：正數的反碼是本身，負數的反碼保持符号位不變，其他位逐位取反

3.補碼

首先，我們來看為什麼會出現補碼，我們先來看2個問題

第一，0居然用2個編碼（+0和-0）來表示了：

原碼：[0000 0000]原 = [1000 0000]原

反碼：[0000 0000]反 = [1111 1111]反

第二，我們來看一個現象

1 + （-1）

= [00000001]原 + [1000 0001]原

= [10000010]原

= -2

明顯是不對的！

反碼：

1 + （-1）

= [00000001]反 + [1111 1110]反

= [1111 1111]反

= -0

表現的好詭異！（正常應該是 0000 0000）

為了解決這些問題，我們在計算機體系中引入了補碼。

現在我們來看補碼怎麼取：

我們用第一位表示符号（0為非負數，1為負數），剩下的位非負數保持不變，負數按位求反末位加一。

[+8] = [00001000]原 = [0000 1000]補

[-8] = [10001000]原 = [1111 0111]反 = [1111 1000]補

即：正數的補碼是自己本身，負數的補碼口訣為：逐位取反，末位加1

引進了補碼之後，我們看看計算的情況：

1 + （-1）

= [00000001]補 + [1111 1111]補

= [0000 0000]補

= 0

很明顯，通過這樣的方式，計算機進行運算的時候，就不用關心符号這個問題，而隻需要按照統一的逢二進一的原則進行運算就可以了。

好了，補充了這些知識之後，可以進入正題了。

二、zigzag壓縮算法

前文說到了，在絕大多數情況下，我們使用到的整數，往往是比較小的。然而，我們為了正确，又不得不把很多無用的0進行傳輸。Base 128 Varints編碼很好地解決了上面說的問題，但是，如果傳輸的數字出現了負數，會出現什麼情況呢？

依然舉個很簡單的例子，假設我要傳輸數字-1，會怎樣傳輸呢？

[-1]=[10000000 00000000 00000000 00000001]原 = [11111111 11111111 11111111 11111110]反 = [11111111 11111111 11111111 11111111]補

前面的廢物0，到這裡居然變成了廢物1了，怎麼樣才能進行壓縮呢？

zigzag給出了一個很巧的方法：我們之前講補碼講過，補碼的第一位是符号位，他阻礙了我們對于前導0的壓縮，那麼，我們就把這個符号位放到補碼的最後，其他位整體前移一位：

-1= [11111111_11111111_11111111_11111111]補= [11111111_11111111_11111111_11111111]符号後移

但是即使這樣，也是很難壓縮的，因為數字絕對值越小，他所含的前導1越多。于是，這個算法就把負數的所有資料位按位求反，符号位保持不變，得到了這樣的整數：

-1= [11111111_11111111_11111111_11111111]補= [11111111_11111111_11111111_11111111]符号後移=[00000000_00000000_00000000_00000001]符号後移

我們熟悉的前面的一堆0又出現了，又可以愉快地使用Base 128 Varints算法進行編碼了。

那麼，如果是正數的情況，這個算法改怎麼處理呢？如果數字是正數，符号位一樣放到最後，其他資料全部保持不變就行了，例如：

[1]

= (00000000_00000000_00000000_00000001)補

= (00000000_00000000_00000000_00000010)符号後移

= (00000000_00000000_00000000_00000010)zigzag

這樣一弄，正數、0、負數都有同樣的表示方法了，我們就可以對小整數進行壓縮了