1. BitMap介紹

BitMap可以理解為通過一個bit數組來存儲特定數據的一種數據結構。BitMap常用于對大量整形數據做去重和查詢。
在這類查找中，我們可以通過map數據結構進行查找。但如果數據量比較大map數據結構將會大量占用內存。
BitMap用一個比特位來映射某個元素的狀態，所以這種數據結構是非常節省存儲空間的。

BitMap用途

• BitMap用于數據去重
  BitMap可用于數據的快速查找，判重。
• BitMap用于快速排序
  BitMap由于其本身的有序性和唯一性，可以實現快速排序：將其加入bitmap中，然后再遍歷獲取出來，從而得到排序的結果。

如何判斷數字在bit數組的位置

在后面的代碼中，我們使用[]byte來存儲bit數據，由于一個byte有8個二進制位。因此：

• 數字/8=數字在字節數組中的位置。
• 數字%8=數字在當前字節中的位置。
  例如：數字10，
• 10/8=1，即數字10對應的字節數組的位置為：1
• 10%8=2，即數字10對應的當前字節的位置為：2

設置數據到bit數組

• num/8得到數字在字節數組中的位置 => row
• num%8得到數字在當前字節中的位置 => col
• 將1左移col位，然后和以前的數據做|運算，這樣就可以將col位置的bit替換成1了。

從bit數組中清除數據

• num/8得到數字在字節數組中的位置 => row
• num%8得到數字在當前字節中的位置 => col
• 將1左移col位，然后對取反，再與當前值做&，這樣就可以將col位置的bit替換成0了。

數字是否在bit數組中

• num/8得到數字在字節數組中的位置 => row
• num%8得到數字在當前字節中的位置 => col
• 將1左移col位，然后和以前的數據做&運算，若該字節的值!=0，則說明該位置是1，則數據在bit數組中，否則數據不在bit數組中。

2. Go語言位運算

在Go語言中支持以下幾種操作位的方式：

• & 按位與：兩者全為1結果為1，否則結果為0
• | 按位或：兩者有一個為1結果為1，否則結果為0
• ^ 按位異或：兩者不同結果為1，否則結果為0
• &^ 按位與非：是"與"和"非"操作符的簡寫形式
• <<?按位左移：
• >>?按位右移：

左移

將二進制向左移動，右邊空出的位用0填補，高位左移溢出則舍棄該高位。
由于每次移位數值會翻倍，所以通常用代替乘2操作。當然這是建立在移位沒有溢出的情況。
例如：1<<3 相當于1×8=8，3<<4 相當于3×16=48

右移

將整數二進制向右移動，左邊空出的位用0或者1填補。正數用0填補，負數用1填補。
負數在內存中的二進制最高位為符號位——使用1表示，所以為了保證移位之后符號位的正確性，所以需要在高位補1。
相對于左移來說，右移通常用來代替除2操作。
例如：24>>3 相當于24÷8=3

使用&^和位移運算來給某一位置0

這個操作符通常用于清空對應的標志位，例如 a = 0011 1010，如果想清空第二位，則可以這樣操作:
a &^ 0000 0010 = 0011 1000

3. BitMap的Go語言實現

接下來我們給出BitMap的Go語言實現，目前代碼已經上傳到github中，下載地址

定義

首先給出BitMap結構的定義：

type BitMap struct {
    bits []byte
    vmax uint
}

創建BitMap結構

func NewBitMap(max_val ...uint) *BitMap {
    var max uint = 8192
    if len(max_val) > 0 && max_val[0] > 0 {
        max = max_val[0]
    }
    bm := &BitMap{}
    bm.vmax = max
    sz := (max + 7) / 8
    bm.bits = make([]byte, sz, sz)
    return bm
}

將數據添加到BitMap

func (bm *BitMap)Set(num uint) {
    if num > bm.vmax {
        bm.vmax += 1024
        if bm.vmax < num {
            bm.vmax = num
        }
        dd := int(num+7)/8 - len(bm.bits)
        if dd > 0 {
            tmp_arr := make([]byte, dd, dd)
            bm.bits = append(bm.bits, tmp_arr...)
        }
    }
    //將1左移num%8后，然后和以前的數據做|，這樣就替換成1了
    bm.bits[num/8] |= 1 << (num%8)
}

從BitMap中刪除數據

func (bm *BitMap)UnSet(num uint) {
    if num > bm.vmax {
        return
    }
    //&^:將1左移num%8后，然后進行與非運算，將運算符左邊數據相異的位保留，相同位清零
    bm.bits[num/8] &^= 1 << (num%8)
}

判斷BitMap中是否存在指定的數據

func (bm *BitMap)Check(num uint) bool {
    if num > bm.vmax {
        return false
    }
    //&:與運算符，兩個都是1，結果為1
    return bm.bits[num/8] & (1 << (num%8)) != 0
}