protobuf是怎樣實現的?
首先,我們來思考最簡單的情況,該怎樣表示數字。
你可能會想這還不簡單,統一用固定長度,比如用64個比特(8字節),這種方法可行,但問題是不論一個數字有多小,比方2,那么用這種方法表示2也需要占據64個比特(8字節):
明明只要一個字節就能表示而我們卻用了8個,前面的全都是0,這也太奢侈太浪費了吧。
顯然,在這里我們不能使用固定長度來表示數字,而需要使用變長方法來表示。
什么叫變長?意思是說如果數字本身比較大,那么其使用的比特位可以較多,但如果數字很小那么就應該使用較少的比特位來表示,這就叫變長,隨機應變,不死板。
那怎樣變長呢?
我們規定:對于每一個字節來說,第一個比特位如果是1那么表示接下來的一個比特依然要用來解釋為一個數字,如果第一個比特為0,那么說明接下來的一個字節不是用來表示該數字的。
也就是說對于每個8個比特(1字節)來說,它的有效載荷是7個比特,第一個比特僅僅用來標記是否還應該把接下來的一個字節解析為數字。
根據這個規定假設來了這樣一串01二進制:
1010110000000010
根據規定,我們首先取出第一個字節,也就是:
10101100
此時我們發現第一個比特位是1,因此我們知道接下來的一個字節也屬于該數字,將當前字節的1去掉就是:
0101100
然后我們看下一個字節:
00000010
我們發現第一個bit為0,因此我們知道下一個字節不屬于該數字了。
接下來我們將解析到的0101100(第一個字節去掉第一個比特位)以及第二個字節0000010(第二個字節去掉第一個比特位)翻轉之后拼接到一起,這里之所以翻轉是因為我們規定數字的高位在后。
這個過程就是:
1010110000000010
-> 10101100 | 00000010 // 解析得到兩個字節
_ _
-> 0101100 | 0000010 // 各自去掉最高位
-> 0000010 | 0101100 // 兩個字節翻轉順序
0000010 + 0101100
-> 100101100 // 拼接
最后我們得到了100101100,這一串二進制表示數字300。
這種數字的變長表示方法在protobuf中被稱之為varint。
因此在這種表示方法下,如果數字較大,那么使用的比特就多,如果數字較小那么使用比特就少,聰明吧。
有的同學看到這里可能會問題,剛才講解的方法只能表示無符號數字,那么有符號數字該怎么表示呢?比如-2該怎么表示?
有符號數的表示
按照剛才變長編碼的思想,-2147483646使用的比特位應該比-2要少。
然而我們知道在計算機世界中負數使用補碼表示的,也就是說最高位(最左側的比特位)一定是1,假設我們使用64位來表示數字,那么如果我們依然用補碼來表示數字的話那么無論這個負數有多大還是多小都需要占據10個字節的空間。
為什么是10個字節呢?
不要忘了varint每個字節的有效負荷是7個比特,那么對于需要64位表示的數字來說就需要64/7向上取整也就是10個字節來表示。
這顯然不能滿足我們對數字變長存儲的要求。
該怎么解決這個問題呢?
既然無符號數字可以方便的進行變長編碼,那么我們將有符號數字映射稱為無符號數字不就可以了 ,這就是所謂的ZigZag編碼,是不是很聰明,就像這樣:
原始信息 編碼后
0 0
-1 1
1 2
-2 3
2 4
-3 5
3 6
... ...
2147483647 4294967294
-2147483648 4294967295
這樣我們就可以將有符號數字轉為無符號數字,接收方接收到該數據后再恢復出有符號數字。
現在數字的問題徹底解決了,但這僅僅是萬里長征第一步。
-
計算機
+關注
關注
19文章
7626瀏覽量
90106 -
Server
+關注
關注
0文章
94瀏覽量
24513 -
網絡編程
+關注
關注
0文章
72瀏覽量
10486
發布評論請先 登錄
什么是二進制計數器,二進制計數器原理是什么?
二進制電平,什么是二進制電平
二進制編碼的十進制表示轉換解碼器

二進制如何轉換為十進制?
二進制解碼器到底是什么

評論