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

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

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

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

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

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

那怎樣變長(zhǎng)呢？

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

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

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

1010110000000010

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

10101100

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

0101100

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

00000010

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

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

這個(gè)過(guò)程就是：

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

    0000010  +  0101100
->  100101100           // 拼接

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

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

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

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

有符號(hào)數(shù)的表示

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

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

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

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

這顯然不能滿足我們對(duì)數(shù)字變長(zhǎng)存儲(chǔ)的要求。

該怎么解決這個(gè)問(wèn)題呢？

既然無(wú)符號(hào)數(shù)字可以方便的進(jìn)行變長(zhǎng)編碼，那么我們將有符號(hào)數(shù)字映射稱(chēng)為無(wú)符號(hào)數(shù)字不就可以了 ，這就是所謂的ZigZag編碼，是不是很聰明，就像這樣：

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

...          ...

2147483647   4294967294
-2147483648  4294967295

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

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