Go 實現的一個 bitset，設計思想非常棒，值得參考收藏！

這兩日讀了一個實現二維碼生成的庫。其中的 bitset 設計得非常好，就摘抄記錄下來，與大家一起分享。

bitset 實現一個可擴展的 bit 集合，可以添加 bit 和查看 bit。它在二維碼生成中，用來將編碼後的內容協助生成位圖，然後通過位圖進行繪製二維碼。二維碼的黑白格子正好用二進制 0 和 1 來表示。

下面開始詳細講解這個功能設計：

一、我們使用一個結構體來存儲 bit 序列。Bitset 是一個結構體，它有兩個字段，numBits int，用來記錄有多少 bit 存儲，bits []byte，用來存儲 bits。這是我感覺設計比較好的第一個地方，使用 []byte 來存儲 bits。

// Bitset stores an array of bits.
type Bitset struct {
  // The number of bits stored.
  numBits int
  // Storage for individual bits.
  bits []byte
}

二、創建一個 bitset 實例，可以使用 bitset.New() 來新生成一個 Bitset。函數的原型和實現爲：

func New(v ...bool) *Bitset {
  b := &Bitset{numBits: 0, bits: make([]byte, 0)}
  b.AppendBools(v...)
  return b
}

這是我認爲第二個比較好的地方。使用 bool 來表示 bit 0 和 bit 1。在 Golang 中，沒有直接表示 bit 的類型。而 bool 有兩個值，true 或者 false。它對應 bit 0 或 1，並且 bool 在內存中僅用一個字節表示，也比較節省內存。如果使用 int 表示，那麼太耗費內存，如果使用 byte 表示，轉換也不方便，最妙的地方，在於獲取 bit 序列中的某個值時，它獲取到的是 bool 值，可以直接進行 if 判斷。例如畫黑格子還是白格子，非常的方便。

在 New 函數中，除了初始化內存外，還調用了方法 AppendBools，參數是可變參數。如果是 b.AppendBools(true, true, false)  ，則表示爲 {1, 1, 0}，那麼它是如何實現的，我們來看看：

// AppendBools appends bits to the Bitset.
func (b *Bitset) AppendBools(bits ...bool) {
  b.ensureCapacity(len(bits))
  for _, v := range bits {
    if v {
      b.bits[b.numBits/8] |= 0x80 >> uint(b.numBits%8)
    }
    b.numBits++
  }
}

它調用了方法，ensureCapacity()，這個方法確保容量足夠。下面再細細講解。迭代循環可變參數，當參數爲 true 時，將 bits 數組中對應的字節對應位進行更新，然後自增 bit 計數。

其中 b.numBits/8 算出的是商，可以算出在 bits 數組中的索引。b.numBits%8 算出的是餘數，可以算出在所對應的 byte 中的偏移。

 b.bits[b.numBits/8] |= 0x80 >> uint(b.numBits%8)

我們再看下 ensureCapacity 方法，它的作用是確保 bitset 有足夠的容量可以存儲新添加的 bit。爲了減少頻繁的內存分配，使用了簡單的算法，能夠一次性分配就能夠容納新增加的 bit。這是我認爲比較好的第三個地方。在 Golang 中，我們應該瞭解 append 操作當內存不夠時，會重新進行內存分配，並複製原來的數據。如果直接使用 append 方法，很有可能會進行多次的內存分配。

// ensureCapacity ensures the Bitset can store an additional |numBits|.
//
// The underlying array is expanded if necessary. To prevent frequent
// reallocation, expanding the underlying array at least doubles its capacity.
func (b *Bitset) ensureCapacity(numBits int) {
  numBits += b.numBits
  newNumBytes := numBits / 8
  if numBits%8 != 0 {
    newNumBytes++
  }
  if len(b.bits) >= newNumBytes {
    return
  }
  b.bits = append(b.bits, make([]byte, newNumBytes+2*len(b.bits))...)
}

三、當創建了 bitset 實例後，我們可以繼續添加新的 bit，可以從 byte 數組中添加，從 byte 中添加，從無符號整型中添加。先來說說從 byte 中添加。

// AppendByte appends the numBits least significant bits from value.
func (b *Bitset) AppendByte(value byte, numBits int) {
  b.ensureCapacity(numBits)
  if numBits > 8 {
    log.Panicf("numBits %d out of range 0-8", numBits)
  }
  for i := numBits - 1; i >= 0; i-- {
    if value&(1<<uint(i)) != 0 {
      b.bits[b.numBits/8] |= 0x80 >> uint(b.numBits%8)
    }
    b.numBits++
  }
}

這個方法有兩個參數，一個存儲值的 byte，一個是添加的位數。這個設計非常的妙，你可以只添加幾個 bit。從算法實現中，我們可以看到 bit 是從右開始算起。然後取當前位是否爲 1。從無符號整型中添加，原理如同從 byte 中添加，它可以添加更多的位數，從 byte 切片中添加，是從 byte 中添加的封裝，使用循環實現，可在下面的小程序中查看源碼。

四、當添加完之後，我們可以獲取添加的 bit 數量，以及取出某個 bit 的值，或者一段 bit 的值，或者所有的 bit 的值。這裏一塊講了。

// Len returns the length of the Bitset in bits.
func (b *Bitset) Len() int {
  return b.numBits
}
// Bits returns the contents of the Bitset.
func (b *Bitset) Bits() []bool {
  result := make([]bool, b.numBits)
  var i int
  for i = 0; i < b.numBits; i++ {
    result[i] = (b.bits[i/8] & (0x80 >> byte(i%8))) != 0
  }
  return result
}
// At returns the value of the bit at |index|.
func (b *Bitset) At(index int) bool {
  if index >= b.numBits {
    log.Panicf("Index %d out of range", index)
  }
  return (b.bits[index/8] & (0x80 >> byte(index%8))) != 0
}

上面 Len 方法直接取結構體的 numBits 值，非常快速方便。取所有 bit 的值是通過 bool 切片返回的，這是我認爲非常妙的另一個地方。在 Golang 中，包括其它語言中，對 bool 的判斷，要遠比其它比較操作更方便更爽，它循環所有 bit，然後將 bit 值轉成 bool 值，這裏通過 bit 位操作和 0 比較返回 bool 值。這裏還有一個 Golang 技巧可以提高性能，當你知道某個切片的大小時，可以在 make 時直接填寫容量，這樣可以直接一次性分配該容量的內存，提高總體性能。我們也可以取某個索引值，它的方法是 At 方法，返回切片中某個索引位置的值。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/oITFXTwgiYU1ccnpaLF-5w