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

This article is to share with you the content of example analysis of bitmap algorithm and its application in c #. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

Bitmap algorithm

Bitmap method is the abbreviation of bitmap, the so-called bitmap, is to use each bit to store a certain state, suitable for large-scale data, but the data state is not many cases. It is usually used to determine whether a certain data exists.

Application

1. Give 4 billion unrepeated unsigned integers, unsorted. Give an unsigned integer, how to quickly determine whether a number is in these 4 billion numbers.

Solution: apply for 512MB of memory: a bit bit represents a unsigned int value to read into 4 billion, set the corresponding bit bit to read the number to be queried, and check whether the corresponding bit is 1, 1 means it exists, and 0 means it does not exist.

two。 Using bitmap method to determine whether there are duplicates in × × array

Solution: judging the existence of repetition in the collection is one of the common programming tasks. When the amount of data in the collection is relatively large, we usually want to do fewer scans, so the double loop method is not desirable. Bitmap method is more suitable for this situation. Its practice is to create a new array of length max+1 according to the largest element in the set, max, and then scan the original array again. If you encounter a few, give 1 to the position of the new array. If you encounter 5, set 1 to the sixth element of the new array, so that the next time you encounter 5, you will find that the sixth element of the new array is 1. This shows that the data this time must be duplicated with the previous data. This method of initializing a new array with zero and one after it is similar to the bitmap processing method, so it is called the bitmap method. Its worst case is 2N. The efficiency can be doubled if the maximum value of the array is known and the length of the new array can be set in advance.

3. Use bitmap method to sort × × array

Solution:

First iterate through the array to get the maximum and minimum value of the array, and then narrow the range of bitmap according to this maximum and minimum value. It should be noted that the negative numbers of int should be converted to unsigned int to deal with, and when taking bits, the number should be subtracted from the minimum value.

Apply 1 code to implement:

# pragma once#includetemplatestruct DataType {long long operator () (const T&key) {return key;}}; templatestruct StringType {long long operator () (const string&key) {long long size = 0; for (int I = 0; I < key.size ()) Return size; +) {size + = key [I];} return size;}}; templateclass BitMap {public: BitMap (size_t size = 1) {_ a.resize (size / 32 + 1) } ~ BitMap () {} void set (T & x) {BMFunc bmf; size_t index = bmf (x) / 32; size_t num = bmf (x)% 32; if (!)

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.