研究 Protobuf 時發現一個挺好的演算法 — ZigZag
收錄於《深入微服務》,作者 “老苗”
我原本是想研究 Protobuf 原理呢,但在研究過程中發現 Protobuf 在對負數編碼時使用到了 ZigZag 演算法,所以才有了本篇。當然你不懂 Protobuf 也完全不影響閱讀。
在聊這個演算法之前,我們先聊聊進位制、補碼相關的東西。如果你懂,那就指向往下翻。
該篇程式碼:
http://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 原理理解的重要部分。如果有不懂的,就在下方給我留言!
完整程式碼: