1. varint （數(shù)字）

1.1 評價(jià)

數(shù)字壓縮算法
算法邏輯：每個字節(jié)的首bit代表是否還需要下一位（0表示不需要，1表示需要），每個字節(jié)的可用位為7位

1.2 優(yōu)缺

優(yōu)點(diǎn)：對于int類型數(shù)值較小的數(shù)起到壓縮作用，比如，2的(3*7)次方以下的數(shù)字都能起到壓縮作用，由于實(shí)際傳輸過程中，我們大多用到的都是小類型的int數(shù)值，故這種方法能起到壓縮字符的作用。

缺點(diǎn)：

1. 對于數(shù)值較大的數(shù)字，比如int類型，2的(4*7)次方以上的數(shù)字是需要5個字節(jié)來表示。
2. 對于負(fù)值，如-1，本質(zhì)上首位為1導(dǎo)致數(shù)極大，必須要5個字節(jié)才能表示。

1.3編碼與解析(java)

32位加密算法：

static void write32ForVarint(int value,byte[] buffer,int position){
        while (true) {
            if ((value & ~0x7F) == 0) {
                buffer[position++] = (byte) value;
                return ;
            } else {
                buffer[position++] = (byte) ((value & 0x7F) | 0x80);//|0x80代表首位bit置1
                value >>>= 7;
            }
        }
    }

32位解密算法:

static int read32ForVarint(byte[] buffer,int position){
        int result = 0;
        for (int shift = 0; shift < 32; shift += 7) {//這個32 可以寫29反正只要大于或等于28就行。
            final byte b = buffer[position++];
            result |= (long) (b & 0x7F) << shift;
            if ((b & 0x80) == 0) {
                return result;
            }
        }
        return -1;
    }

2. zigzag （數(shù)字）

2.1 評價(jià)

數(shù)字壓縮算法
由于表示負(fù)數(shù)時(shí)，varint花費(fèi)的字節(jié)太大，所以需要一種彌補(bǔ)辦法，來解決這種沖突!
由于考慮到varint之所以表示負(fù)數(shù)占用字節(jié)大，主要因?yàn)樨?fù)數(shù)表示方法是首位且為1，而varint一般從末尾向前壓縮，所以varint壓縮負(fù)數(shù)通常很大，基于這種考慮，我們想到當(dāng)數(shù)字為負(fù)數(shù)時(shí)，將首位挪到尾位，并按位取反把1全部變?yōu)?。最后在按照varint壓縮字節(jié)，這樣就能夠使得我們可以用少量的字節(jié)表示值小的負(fù)數(shù)。

2.2 優(yōu)缺

優(yōu)點(diǎn)：相較于varint，能夠用少量字節(jié)表示負(fù)數(shù)。
缺點(diǎn)：對于數(shù)值大的的正數(shù)或特別小的負(fù)數(shù)仍然需要大很多的字節(jié)數(shù)，且解析相較于varint需要更多邏輯。

2.3編碼與解析(java)

編碼: 先轉(zhuǎn)換int，然后在帶入varint編碼

static int transform32ForZigzag(int num){
    return (num << 1) ^ (num >> 31);//看清楚"^" 在java代表抑或的意思
}

解碼：先用varint解碼，然后轉(zhuǎn)換int

static int detransform32ForZigzag(int num){
    return (num >>> 1) ^ -(num & 1);
}

3. UTF-8變長方案

3.1評價(jià)

字符編碼方案

對于某一個字符的UTF-8編碼，如果只有一個字節(jié)則其最高二進(jìn)制位為0；如果是多字節(jié)，其第一個字節(jié)從最高位開始，連續(xù)的二進(jìn)制位值為1的個數(shù)決定了其編碼的位數(shù)，其余各字節(jié)均以10開頭。UTF-8最多可用到6個字節(jié)。
如表：
1字節(jié) 0xxxxxxx
2字節(jié) 110xxxxx 10xxxxxx
3字節(jié) 1110xxxx 10xxxxxx 10xxxxxx
4字節(jié) 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
5字節(jié) 111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
6字節(jié) 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
因此UTF-8中可以用來表示字符編碼的實(shí)際位數(shù)最多有31位，即上表中x所表示的位。除去那些控制位（每字節(jié)開頭的10等），這些x表示的位與UNICODE編碼是一一對應(yīng)的，位高低順序也相同。
整個方案顯得特別的臃腫，很難理解是什么考慮下回用到這種臃腫的方案，簡直讓人窒息!

3.2優(yōu)缺

優(yōu)點(diǎn)：幾乎統(tǒng)一了編碼
缺點(diǎn)：臃腫的讓人窒息

3.3編解碼

解碼

static int encode(int unicode,byte[] bytes,int position){
  if(unicode < (int)Math.pow(2,7)){
      bytes[position++] = (byte)unicode & 0x7f;
      return position;
  }
  else if(unicode < (int)Math.pow(2,5+6)){
      byte[position++] = (byte)(unicode & 0xbf | 0x80);
      byte[position++] = (byte)(unicode >> 6) & 0x1f | 0xdf ;
      return position;
  }
  else if 
    //some code
}

編碼：

static String utf8Decode (byte[] bytes){
  char[] chars = new char[bytes.length];//最多不可能超過bytes.length
int charsLen = 0;
  for(int i=0;i<bytes.length;i++){
      byte tmp = bytes[i];
      if(tmp & 0x80 == 0x80){
          chars[charsLen++] = bytes[i] & 0x3f;
      } else {
          //some code
      }
  }
}

4. MQTT剩余長度方案 （數(shù)字）

4.1介紹

和varint方案基本一致，最高位做符號位，符號位1表示最高位為前面還有值，否則為0，則表示結(jié)束

分別表示（每個字節(jié)的低7位用于編碼數(shù)據(jù)，最高位是標(biāo)志位）

4.2優(yōu)缺

和varint一樣

4.3編解碼

netty解碼：

int remainingLength = 0;//剩下長度
int multiplier = 1;
short digit;
int loops = 0;
    do {
    digit = buffer.readUnsignedByte();//讀取一個無符號的byte用short來存;
    remainingLength += (digit & 127) * multiplier;
    multiplier *= 128;
    loops++;
} while ((digit & 128) != 0 && loops < 4);

參考：

1. 詳細(xì)談了 zigzag 算法
2. 對 protoBuf中的 varint ，zigzag算法做了介紹
3. 詳細(xì)談了 protoBuf中varint，zigzag的優(yōu)點(diǎn)和缺點(diǎn)等