Basic principles of Bitmap

A Bitmap is an algorithm that uses binary bits to store data. Since a binary bit can only be 0 or 1, we can use 0 to indicate that the data does not exist and 1 to indicate that the data does exist.

Assuming 1 byte of memory space, you can store 8 pieces of data ranging from 0 to 7, none of which exists at first (the decimal number represented as 0). Since the left side of the binary is high and the right side is low, the first position (the highest bit) corresponds to 7.

Insert data

Now to insert data 2, the corresponding binary bit is changed to 1, and the decimal number represented is 4.

Then insert 3 and 6 respectively, and the result is as follows:

Delete the data

If you want to delete some data, first find the location of the data, and then change the corresponding binary bit to 0.

To find the

To find out whether a data exists, you only need to determine whether the corresponding binary bit is 1. In addition to looking up individual data, you can perform some complex collection operations.

masked

Suppose I have two bitmaps, map1 and map2, and their stores are as follows

A new bitmap is obtained by finding the intersection of the bitmaps of the two bitmaps in bitwise with (&). The second bit is 1, which means that 2 is the intersection of the two bitmaps.

  01001100 
& 00110101
= 00000100
Copy the code

O and set

Through the bitwise or (|) ask two bitmap, get a new bitmap; Intersection of [0 6]

  01001100 
| 00110101
= 01111101
Copy the code

How to modify data

For an 8-bit Bitmap, either insertion or deletion involves modifying one of the bits of data. Given a bitIndex of binary bits (the data operated on),

To change it to 1, use the following formula,

bitmap |= (1 << bitIndex)
Copy the code

1 << bitIndex Is a binary number whose bitIndex bit is 1 and all other bits are 0. By bitwise or, we can guarantee that regardless of the value of bitIndex bit in the original bitmap, the value of bitIndex bit will be 1 in the end, while the value of other bits will remain the same.

For example, bitIndex = 4, bitmap = [01001100], the result is [01011100].

In the same way, if we want to change it to 0, we use the following formula,

bitmap &= ~(1 << bitIndex)
Copy the code

conclusion

In practical applications, the data stored in bitmap can be a large number of integer data, can also represent the user ID and so on.

Bitmaps are applicable to scenarios where a large amount of data is used to quickly remove and locate data and save storage space to the maximum.

In fact, we can’t create an array of bits directly because memory is allocated in at least 1 byte. Java can use byte[],int[],long[], etc. Java also provides a concrete implementation of Bitmap: java.util.bitset.

On BitSet source principles and instructions, later in detail.