Shulou(Shulou.com)06/01 Report--

This article shares with you the content of an example analysis of the BitMap algorithm. Xiaobian thinks it is quite practical, so share it with everyone for reference. Let's follow Xiaobian and have a look.

BitMap

BitMap is to mark the value of an element with a bit, and key is the element. Since BitMap uses bit bits to store data, it can greatly save storage space.

1. Basic idea of BitMap

A simple example to introduce BitMap algorithm principle. Suppose you want to sort 5 elements [4,7,2,5,3] from 0-7 (elements are not duplicated). We can use BitMap algorithm to achieve sorting purposes. To represent 8 numbers, we need 8 bits.

1. First, we open up a byte (8bit) space and set all bits of these spaces to 0.

2. Then we iterate through the five elements, the first element is 4, because the bottom starts with 0, so we set the value of the fifth byte to 1;

3. Then process the remaining four elements, and the final 8 bytes are as follows:

4. Now we traverse the bytes field once and output the position of the byte with value 1 (2, 3, 4, 5, 7), thus achieving the purpose of sorting.

II. Solutions

1. First determine the storage space for each number. For example, each number of int32 type requires 32 bits of storage space, and there are 2^32 numbers in total. It takes 2^32=4G of continuous memory space to express all numbers one by one.

2. If the required memory space is small enough or can meet the computational requirements, directly use the BitMap algorithm to traverse each number i and set a[i] to 1.

3. Sort the keys of a or find a key, depending on the situation.

Thank you for reading! About "BitMap algorithm example analysis" This article is shared here, I hope the above content can be of some help to everyone, so that everyone can learn more knowledge, if you think the article is good, you can share it to let more people see it!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.