研究 Protobuf 時發現一個挺好的算法 — ZigZag
我原本是想研究 Protobuf 原理呢，但在研究過程中發現 Protobuf 在對負數編碼時使用到了 ZigZag 算法，所以才有了本篇。當然你不懂 Protobuf 也完全不影響閱讀。
在聊這個算法之前，我們先聊聊進制、補碼相關的東西。如果你懂，那就指向往下翻。
該篇代碼：
https://github.com/miaogaolin/gofirst/tree/main/zigzag
進制
所謂進制，就是當某一位上的信息滿時，需要往前進位。比如，十進制，就是當某一位上的數滿十時進位；而某一位上的數滿二時進位就是二進制，等等。
進位之間都可以相互轉化，例如：
十進制：10 → 二進制：1010 → 十六進制：A
我之前看過一個答案，說：為什么十進制比較通用？
因為咱人類只有 10 個手指頭，數一遍剛好十個數，所以十進制自然就成為默認的進制。那如果人類長 11 手指頭，說不定就是十一進制。
后來計算機的出現，一個數據的有無是最天然的信息承載單元，所以由 0 和 1 組成的二進制很自然成為計算機的進制方式。在此基礎上，為了方便信息的使用，又采用了八進制、十六進制。
好了，進制這個東西就聊到這了。
三個東西
下來我們對一個十進制正整數表示為二進制，例如：十進制 10 等于二進制 1010。
那如果二進制表示一個負數，該怎么辦？下來我們聊聊。
在計算機的世界里，定義了原碼、反碼和補碼這幾個東西。為了下來講解簡單點，我們假設使用一個字節（1Byte=8bits）表示一個數。
1. 原碼
我們用第一個位表示符號（ 0 為非負數，1 為負數），剩下的位表示值。例如：
+8 → 原：00001000
-8 → 原: 10001000
2. 反碼
我們用第一位表示符號（ 0 為非負數，1 為負數），剩下的位，非負數保持不變，負數按位求反。例如：
+8 → 原：0000 1000 → 反：0000 1000
-8 → 原：1000 1000 → 反：1111 0111
如果我們用原碼或者補碼來表示整數的二進制，有什么問題嗎？表面上看，似乎挺好的。不過仔細思考就會發現兩個問題：
第一，0 居然可以用兩個編碼表示，+0 和 -0。
原：0000 0000 → 1000 0000
反：0000 0000 → 1111 1111
第二，計算機不知道符號位的存在，因此參加運算后，會出現一個奇怪的現象。
原碼
1 + (-1)
→ 0000 0001 + 1000 0001
→ 1000 0010
→ -2
明顯是不對的！
反碼
1 + (-1)
→ 0000 0001 + 1111 111
→ 1111 1111
→ -0
這看起來也怪怪的。
因此，為了解決這些問題，我們在計算機體系中引入了補碼。
3. 補碼
我們用第一位表示符號（ 0 為非負數，1 為負數），剩下的位非負數保持不變，負數按位求反末位加一。
+8 → 原：0000 1000 → 補：0000 1000
-8 → 原：1000 1000 → 補：1111 1000
現在我們看看，把符號帶進去運算會出現什么結果？
1 + (-1)
→ 0000 0001 + 1111 1111
→ 0000 0000
→ 0
很明顯，通過這樣的方式，計算機進行運算的時候，就不用關心符號這個問題，統一都按照滿 2 進 1 規則處理。
好了，進制和補碼的知識就說到這了，下來進入真正的主題。
ZigZag
在大多數情況下，我們使用到的整數往往會比較小。
而我們為了在系統通訊時便于傳輸，往往需要一個整形（int32、int64）作為基本的傳輸類型。
因此在大多數系統中，以 4 Bytes 和 8 Bytes 來表示。這樣，為了傳輸一個整型 1，我們需要傳輸 “00000000 00000000 00000000 00000001” 32 個 bits，而有價值的數據只有 1 位，剩下的都是浪費呀！
那怎么辦呢？ZigZag 應用而生。那這個算法具體的思想是怎么樣的呢？
對于正整數來講，如果在傳輸數據時，我們把多余的 0 去掉，或者盡可能的減少無意義的 0。那么我們是不是就可以將數據進行壓縮？那怎樣進行壓縮？
答案也很簡單，例如 00000000 00000000 00000000 00000001 這個數。如果我們只發送 1 位 或者 1 字節 00000001，是不是就會很大程度減少無用的數據？
當然，如果這個世界上只有正整數，那我們就可以方便的做到這一點。可惜，他居然存在負數！那負數如何表示？
例如，十進制 -1 的補碼表示為 11111111 11111111 11111111 11111111。
可以看到，前面全是 1，你說怎么弄？
ZigZag 給出了一個很巧妙的方法。我們之前講補碼說過，補碼的第一位是符號位，他阻礙了我們對于前導 0 的壓縮，那么，我們就把這個符號位放到補碼的最后，其他位整體前移一位。
補：** 1 **1111111 11111111 11111111 11111111
→ 符號后移：11111111 11111111 11111111 111111** 1 **
但是即使這樣，也是很難壓縮的。于是，這個算法就把負數的所有數據位按位求反，符號位保持不變，得到了這樣的整數，如下：
十進制：-1
→ 補：** 1 **1111111 11111111 11111111 11111111
→ 符號后移：11111111 11111111 11111111 1111111** 1 **
→ ZigZag：00000000 00000000 00000000 0000000** 1 **
而對于非負整數，同樣的將符號位移動到最后，其他位往前挪一位，數據保持不變，如下：
十進制：1
→ 補：** 0 **0000000 00000000 00000000 00000001
→ 符號后移：00000000 00000000 00000000 0000001** 0 **
→ ZigZag：00000000 00000000 00000000 0000001** 0 **
這樣一弄，正數、0、負數都有同樣的表示方法了。我們就可以對小整數進行壓縮了，對吧~
于是，就可以寫成如下的代碼：
- func int32ToZigZag(n int32) int32 {
- return (n << 1) ^ (n >> 31)
- }
n << 1 將整個值左移一位，不管正數、0、負數他們的最后一位都會變成了 0。講解如下：
十進制：1
→ 補：** 0 **0000000 00000000 00000000 00000001
→ 左移一位：00000000 00000000 00000000 00000010
十進制：-1
→ 補：** 1 **1111111 11111111 11111111 11111111
→ 左移一位：11111111 11111111 11111111 11111110
n >> 31 將符號位放到最后一位。如果是非負數，則為全 0；如果是負數，就是全 1。講解如下：
十進制：1
→ 補：** 0 **0000000 00000000 00000000 00000001
→ 右移 31 位：00000000 00000000 00000000 0000000** 0 **
十進制：-1
→ 補：** 1 **1111111 11111111 11111111 11111111
→ 右移 31 位：11111111 11111111 11111111 1111111** 1 **
最后這一步很巧妙，將兩者進行按位異或操作。
十進制：1
→ n << 1 ：00000000 00000000 00000000 00000010 ^
n >> 31 ： 00000000 00000000 00000000 0000000** 0 **
→ 00000000 00000000 00000000 0000001** 0 **
可以看到最終結果，數據位保持不變，而符號位也保持不變，只是符號位移動到了最后一位。
十進制：-1
→ n << 1 ：11111111 11111111 11111111 11111110 ^
n >> 31 ：11111111 11111111 11111111 1111111** 1 **
→ 00000000 00000000 00000000 0000000** 1 **
可以看到，數據位全部反轉了，而符號位保持不變，且移動到了最后一位。這一步真的寫的很巧妙！
ZigZag 還原代碼如下：
- func toInt32(zz int32) int32 {
- return int32(uint32(zz)>>1) ^ -(zz & 1)
- }
類似的，我們還原的代碼就反過來寫就可以了。不過這里要注意一點，就是右移的時候，需要用不帶符號的移動，否則如果第一位是 1 的時，移動時會補1。所以，使用了無符號的移位操作 uint32(zz)>>1 。
好了，有了該算法，就可以得到一個有前導 0 的整數。只是，該數據依然使用 4 字節存儲。下來我們要考慮如何盡可能的減少字節數，并且還能還原。
例如，我們將 1 按照如上算法轉化得到：00000000 00000000 00000000 00000010。
下來我們最好只需要發送 2 bits（10），或者發送 8 bits（00000010），把前面的 0 全部省掉。因為數據傳輸是以字節為單位，所以，我們最好保持 8 bits這樣的單位。所以我們有 2 種做法：
我們可以額外增加一個字節，用來表示接下來有效的字節長度，比如：00000001 00000010，前 8 位表示接下來有 1 個字節需要傳輸，第二個 8 位表示真正的數據。這種方式雖然能達到我們想要的效果，但是莫名的增加一個字節的額外浪費。有沒有不浪費的辦法呢？
字節自表示方法。ZigZag 引入了一個方法，就是用字節自己表示自己。具體怎么做呢？我們來看看代碼。
- func compress(zz int32) []byte {
- var res []byte
- size := binary.Size(zz)
- for i := 0; i < size; i++ {
- if (zz & ^0x7F) != 0 {
- res = append(res, byte(0x80|(zz&0x7F)))
- zz = int32(uint32(zz) >> 7)
- } else {
- res = append(res, byte(zz&0x7F))
- break
- }
- }
- return res
- }
大家先看看代碼里那個 ^0x7F，他究竟是個什么數呢？
^0x7F：11111111 11111111 11111111 10000000
他就是從倒數第八位開始，高位全為 1 的數。他的作用就是去除最后七位后，判斷還有沒有信息。
我們把 ZigZag 值傳遞給這個函數，這個函數就將這個值從低位到高位切分成每 7 bits 一組，如果高位還有有效信息，則給這 7 bits 補上 1 個 bit 的 1（0x80）。如此反復 直到全是前導 0，便結束算法。
舉個例來講：
十進制：-1000
→ 補：** 1 **1111111 11111111 11111100 00011000
→ ZigZag：00000000 00000000 00000111 1100111** 1 **
我們先按照七位一組的方式將上面的數字劃開，0000 0000000 0000000 0001111 1001111。
詳細步驟如下：
他跟 ^0x7F 做與操作的結果，高位還有信息，所以，我們把低 7 位取出來，并在倒數第八位上補一個 1（0x80）：11001111。
將這個數右移七位，0000 0000000 0000000 0000000 0001111。
再取出最后的七位，跟 ^0x7F 做與操作，發現高位已經沒有信息了（全是0），那么我們就將最后 8 位完整的取出來：00001111，并且跳出循環，終止算法。
最終，我們就得到了兩個字節的數據 [11001111, 00001111]。
通過上面幾步，我們就將一個 4 字節的 ZigZag 變換后的數字變成了一個 2 字節的數據。如果我們是網絡傳輸的話，就直接發送這 2 個字節給對方進程。對方進程收到數據后，就可以進行數據的組裝還原了。具體的還原操作如下：
- func decompress(zzByte []byte) int32 {
- var res int32
- for i, offset := 0, 0; i < len(zzByte); i, offset = i+1, offset+7 {
- b := zzByte[i]
- if (b & 0x80) == 0x80 {
- res |= int32(b&0x7F) << offset
- } else {
- res |= int32(b) << offset
- break
- }
- }
- return res
- }
整個過程就和壓縮的時候是逆向的，對于每一個字節，先看最高一位是否有 1（0x80）。如果有，就說明不是最后一個數據字節包，那取這個字節的最后七位進行拼裝。否則，說明就是已經到了最后一個字節了，那直接拼裝后，跳出循環，算法結束。最終得到 4 字節的整數。
結語
算法不是很復雜，遇到哪塊不懂了，就好好觀察想想，這也是對 Protobuf 原理理解的重要部分。如果有不懂的，就在下方給我留言！
完整代碼：
https://github.com/miaogaolin/gofirst/tree/main/zigzag
