Go data structure and algorithm BitMap principle and implementation example

1. Introduction to BitMap

BitMap can be understood as a data structure that stores specific data through a bit array. BitMap is often used to deduplicate and query large amounts of plastic surgery data.
In this type of search, we can search through the map data structure. However, if the data volume is relatively large, the map data structure will occupy a lot of memory.
BitMap uses a bit to map the state of an element, so this data structure is very storage space-saving.

BitMap usage

BitMap is used for data deduplication
BitMap can be used for quick data search and verification.
BitMap for quick sorting
Due to its orderliness and uniqueness, BitMap can achieve quick sorting: add it to the bitmap, and then traverse it to get it out to get the sorted result.

How to determine the position of a number in a bit array

In the following code, we use []byte to store bit data, since a byte has 8 binary bits. therefore:

Number/8=The position of the number in the byte array.
Number %8 = the position of the number in the current byte.
For example: the number 10,
10/8=1, that is, the position of the byte array corresponding to the number 10 is: 1
10%8=2, that is, the position of the current byte corresponding to the number 10 is: 2

Set data to bit array

num/8 gets the position of the number in the byte array => row
num%8 gets the position of the number in the current byte => col
Shift 1 left the col bit, and then perform | operation with the previous data, so that the bit of the col position can be replaced with 1.

Clear data from bit array

num/8 gets the position of the number in the byte array => row
num%8 gets the position of the number in the current byte => col
Shift 1 left the col bit, then invert it, and then do & with the current value, so that the bit of the col position can be replaced with 0.

Is the number in the bit array

num/8 gets the position of the number in the byte array => row
num%8 gets the position of the number in the current byte => col
Shift 1 left the col bit, and then perform & operation with the previous data. If the value of the byte !=0, it means that the position is 1, and the data is in the bit array, otherwise the data is not in the bit array.

2. Go bit operation

In Go, the following ways of operating bits are supported:

& bitwise and: both are 1 and the result is 1, otherwise the result is 0
| Bitwise or: One of the two is 1 and the result is 1, otherwise the result is 0
^ Bitwise XOR: The result is 1 for the difference between the two, otherwise the result is 0.
&^ Bitwise and non: is the abbreviation of the "and" and "non" operators
<<bitwise left shift:
>>bitwise to move right:

Move left

Move the binary to the left, fill the bits that are empty on the right with 0, and if the high bit moves and overflows, the high bit will be discarded.
Since the value of each shift doubles, it is usually used instead of multiplying 2. Of course this is based on the situation where the shift does not overflow.
For example: 1<<3 is equivalent to 1×8=8, 3<<4 is equivalent to 3×16=48

Move right

Move the integer binary to the right, and fill the bits that are empty on the left with 0 or 1. Positive numbers are filled with 0, negative numbers are filled with 1.
The highest binary bit of a negative number in memory is the sign bit - used to represent 1, so in order to ensure the correctness of the sign bit after shifting, it is necessary to make up 1 at the high bit.
Compared with left shift, right shift is usually used instead of dividing 2 operations.
For example: 24>>3 is equivalent to 24÷8=3

Use &^ and displacement operations to give a position 0

This operator is usually used to clear the corresponding flag bit, such as a = 0011 1010. If you want to clear the second bit, you can do it like this:
a &^ 0000 0010 = 0011 1000

3. Go language implementation of BitMap

Next we give the Go language implementation of BitMap. The code has been uploaded to github.Download address

definition

First, the definition of BitMap structure is given:

type BitMap struct {
    bits []byte
    vmax uint
}

Create a BitMap structure

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{}
     = max
    sz := (max + 7) / 8
     = make([]byte, sz, sz)
    return bm
}

Add data to BitMap

func (bm *BitMap)Set(num uint) {
    if num &gt;  {
         += 1024
        if  &lt; num {
             = num
        }
        dd := int(num+7)/8 - len()
        if dd &gt; 0 {
            tmp_arr := make([]byte, dd, dd)
             = append(, tmp_arr...)
        }
    }
    //Transfer 1 to num%8, and then do | with the previous data, so replace it with 1.    [num/8] |= 1 &lt;&lt; (num%8)
}

Delete data from BitMap

func (bm *BitMap)UnSet(num uint) {
    if num &gt;  {
        return
    }
    //&^: After shifting 1 left num%8, then performing non-operation, retaining the bits that differ from the left data on the operator, and clearing the same bits    [num/8] &amp;^= 1 &lt;&lt; (num%8)
}

Determine whether the specified data exists in BitMap

func (bm *BitMap)Check(num uint) bool {
    if num &gt;  {
        return false
    }
    //&: and operator, both are 1, and the result is 1    return [num/8] &amp; (1 &lt;&lt; (num%8)) != 0
}

The above is the detailed content of the go data structure and algorithm BitMap principle and implementation example. For more information about go data structure algorithm BitMap, please pay attention to my other related articles!