快捷導(dǎo)航

Java算法之位圖的概念和實(shí)現(xiàn)詳解

更新時間：2023年10月26日 10:44:43 作者：CodeJiao

這篇文章主要介紹了Java算法之位圖的概念和實(shí)現(xiàn)詳解,位圖可以利用每一位來對應(yīng)一個值,比如可以利用int類型的數(shù)去存儲0~31這個集合的數(shù)字,如果該集合內(nèi)的數(shù)字存在,則把對應(yīng)的位設(shè)置位1默認(rèn)為0,需要的朋友可以參考下

位圖的介紹

位圖可以利用每一位來對應(yīng)一個值，比如可以利用int類型的數(shù)去存儲0~31這個集合的數(shù)字。如果該集合內(nèi)的數(shù)字存在，則把對應(yīng)的位設(shè)置位1（默認(rèn)為0）。

在這里插入圖片描述

如果要存儲的集合元素范圍超過了32個，則可以用int數(shù)組去實(shí)現(xiàn)位圖，第一個數(shù)組元素保存0~31的元素，第二個數(shù)組元素保存32~63的數(shù)組元素。

位圖的好處就是可以節(jié)省大量的空間，缺點(diǎn)是實(shí)現(xiàn)比較復(fù)雜。

注意：

并不是說int類型的位圖只可以存儲0~31的集合元素，也可以存儲例如5~36的元素，在存儲的時候設(shè)置一下規(guī)則就行了，1位對應(yīng)5，2位對應(yīng)6，…32位對應(yīng)36。

位圖的實(shí)現(xiàn)

我們先把完整的實(shí)現(xiàn)代碼放在這里，后面會分析里面的具體實(shí)現(xiàn)。

public class BitMap {
    private final long[] bitMap;

    /**
     * 構(gòu)造函數(shù)
     *
     * @param max 位圖存儲著 [0,max]的元素
     */
    public BitMap(int max) {
        bitMap = new long[(max + 64) >> 6];
    }

    /**
     * 往位圖里面添加元素
     *
     * @param num 待添加的元素
     */
    public void add(int num) {
        bitMap[num >> 6] |= (1L << (num & 63));
    }

    /**
     * 刪除位圖里面的元素
     *
     * @param num 待刪除的元素
     */
    public void delete(int num) {
        bitMap[num >> 6] &= ~(1L << (num & 63));
    }

    /**
     * 觀察目標(biāo)元素num在位圖中是存在
     *
     * @param num 目標(biāo)元素
     * @return 存在返回1，否則返回0
     */
    public boolean contains(int num) {
        return (bitMap[num >> 6] & (1L << (num & 63))) != 0;
    }
}

構(gòu)造函數(shù)

代碼實(shí)現(xiàn)：

    /**
     * 構(gòu)造函數(shù)
     *
     * @param max 位圖存儲著 [0,max]的元素
     */
    public BitMap(int max) {
        bitMap = new long[(max + 64) >> 6];
    }

分析：

在這里插入圖片描述

添加元素

代碼實(shí)現(xiàn)：

    /**
     * 往位圖里面添加元素
     *
     * @param num 待添加的元素
     */
    public void add(int num) {
        bitMap[num >> 6] |= (1L << (num & 63));
    }

分析：

在這里插入圖片描述

刪除元素

代碼實(shí)現(xiàn)：

    /**
     * 刪除位圖里面的元素
     *
     * @param num 待刪除的元素
     */
    public void delete(int num) {
        bitMap[num >> 6] &= ~(1L << (num & 63));
    }

分析：

刪除元素與添加元素類似，只是需要把該位置元素設(shè)置為0，而不是1。這里使用&元素去實(shí)現(xiàn)。

在這里插入圖片描述

判斷元素是否存在

代碼實(shí)現(xiàn)：

    /**
     * 觀察目標(biāo)元素num在位圖中是存在
     *
     * @param num 目標(biāo)元素
     * @return 存在返回1，否則返回0
     */
    public boolean contains(int num) {
        return (bitMap[num >> 6] & (1L << (num & 63))) != 0;
    }

分析：

在這里插入圖片描述