中文字幕av专区_日韩电影在线播放_精品国产精品久久一区免费式_av在线免费观看网站

溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

go數據結構和算法BitMap原理是什么

發布時間:2022-07-22 16:13:08 來源:億速云 閱讀:147 作者:iii 欄目:開發技術

本篇內容介紹了“go數據結構和算法BitMap原理是什么”的有關知識,在實際案例的操作過程中,不少人都會遇到這樣的困境,接下來就讓小編帶領大家學習一下如何處理這些情況吧!希望大家仔細閱讀,能夠學有所成!

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&times;8=8,3<<4 相當于3&times;16=48

右移

將整數二進制向右移動,左邊空出的位用0或者1填補。正數用0填補,負數用1填補。
負數在內存中的二進制最高位為符號位&mdash;&mdash;使用1表示,所以為了保證移位之后符號位的正確性,所以需要在高位補1。
相對于左移來說,右移通常用來代替除2操作。
例如:24>>3 相當于24&divide;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
}

“go數據結構和算法BitMap原理是什么”的內容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站,小編將為大家輸出更多高質量的實用文章!

向AI問一下細節

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

AI

雷山县| 广饶县| 太白县| 漯河市| 岑巩县| 中西区| 丹凤县| 咸阳市| 陆川县| 林甸县| 固原市| 比如县| 将乐县| 平顺县| 封开县| 常德市| 惠水县| 依兰县| 民县| 南投市| 界首市| 清涧县| 瓦房店市| 咸丰县| 改则县| 利川市| 西林县| 叶城县| 浪卡子县| 酒泉市| 两当县| 施甸县| 民丰县| 炉霍县| 德化县| 都昌县| 乌海市| 芒康县| 芜湖县| 图木舒克市| 南宫市|