protobuf是怎樣實現(xiàn)的？

首先，我們來思考最簡單的情況，該怎樣表示數(shù)字。

你可能會想這還不簡單，統(tǒng)一用固定長度，比如用64個比特(8字節(jié))，這種方法可行，但問題是不論一個數(shù)字有多小，比方2，那么用這種方法表示2也需要占據(jù)64個比特(8字節(jié))：

明明只要一個字節(jié)就能表示而我們卻用了8個，前面的全都是0，這也太奢侈太浪費了吧。

顯然，在這里我們不能使用固定長度來表示數(shù)字，而需要使用變長方法來表示。

什么叫變長？意思是說如果數(shù)字本身比較大，那么其使用的比特位可以較多，但如果數(shù)字很小那么就應(yīng)該使用較少的比特位來表示，這就叫變長，隨機應(yīng)變，不死板。

那怎樣變長呢？

我們規(guī)定：對于每一個字節(jié)來說，第一個比特位如果是1那么表示接下來的一個比特依然要用來解釋為一個數(shù)字，如果第一個比特為0，那么說明接下來的一個字節(jié)不是用來表示該數(shù)字的。

也就是說對于每個8個比特(1字節(jié))來說，它的有效載荷是7個比特，第一個比特僅僅用來標(biāo)記是否還應(yīng)該把接下來的一個字節(jié)解析為數(shù)字。

根據(jù)這個規(guī)定假設(shè)來了這樣一串01二進制：

1010110000000010

根據(jù)規(guī)定，我們首先取出第一個字節(jié)，也就是：

10101100

此時我們發(fā)現(xiàn)第一個比特位是1，因此我們知道接下來的一個字節(jié)也屬于該數(shù)字，將當(dāng)前字節(jié)的1去掉就是：

0101100

然后我們看下一個字節(jié)：

00000010

我們發(fā)現(xiàn)第一個bit為0，因此我們知道下一個字節(jié)不屬于該數(shù)字了。

接下來我們將解析到的0101100(第一個字節(jié)去掉第一個比特位)以及第二個字節(jié)0000010(第二個字節(jié)去掉第一個比特位)翻轉(zhuǎn)之后拼接到一起，這里之所以翻轉(zhuǎn)是因為我們規(guī)定數(shù)字的高位在后。

這個過程就是：

1010110000000010  
->  10101100 | 00000010 // 解析得到兩個字節(jié)
    _          _
 
->  0101100  |  0000010  // 各自去掉最高位 
->  0000010  |  0101100  // 兩個字節(jié)翻轉(zhuǎn)順序

    0000010  +  0101100
->  100101100           // 拼接

最后我們得到了100101100，這一串二進制表示數(shù)字300。

這種數(shù)字的變長表示方法在protobuf中被稱之為varint。

因此在這種表示方法下，如果數(shù)字較大，那么使用的比特就多，如果數(shù)字較小那么使用比特就少，聰明吧。

有的同學(xué)看到這里可能會問題，剛才講解的方法只能表示無符號數(shù)字，那么有符號數(shù)字該怎么表示呢？比如-2該怎么表示？

有符號數(shù)的表示

按照剛才變長編碼的思想，-2147483646使用的比特位應(yīng)該比-2要少。

然而我們知道在計算機世界中負(fù)數(shù)使用補碼表示的，也就是說最高位(最左側(cè)的比特位)一定是1，假設(shè)我們使用64位來表示數(shù)字，那么如果我們依然用補碼來表示數(shù)字的話那么無論這個負(fù)數(shù)有多大還是多小都需要占據(jù)10個字節(jié)的空間。

為什么是10個字節(jié)呢？

不要忘了varint每個字節(jié)的有效負(fù)荷是7個比特，那么對于需要64位表示的數(shù)字來說就需要64/7向上取整也就是10個字節(jié)來表示。

這顯然不能滿足我們對數(shù)字變長存儲的要求。

該怎么解決這個問題呢？

既然無符號數(shù)字可以方便的進行變長編碼，那么我們將有符號數(shù)字映射稱為無符號數(shù)字不就可以了 ，這就是所謂的ZigZag編碼，是不是很聰明，就像這樣：

原始信息      編碼后
0            0 
-1           1 
1            2
-2           3
2            4
-3           5
3            6

...          ...

2147483647   4294967294
-2147483648  4294967295

這樣我們就可以將有符號數(shù)字轉(zhuǎn)為無符號數(shù)字，接收方接收到該數(shù)據(jù)后再恢復(fù)出有符號數(shù)字。

現(xiàn)在數(shù)字的問題徹底解決了，但這僅僅是萬里長征第一步。