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