Detailed introduction and Simulation of bitmap

Catalog

1. Simple application of bitmap

2. Bitmap massive data search

3.STL Introduction and use of bitmap in

3.1 Introduction to bitmap ：

3.2 Use of bitmap ：

4. Application of bitmap

4.1. Quickly find out whether a data is in a collection

4.2. Sort

4.3. Find the intersection of two sets 、 And set etc.

4.4. Disk block mark in the operating system

(1 Bar message ) Linux File system _ Moon and a half wood Jin's blog -CSDN Blog https://blog.csdn.net/weixin_45897952/article/details/123262685?spm=1001.2014.3001.5501

5. Bitmap simulation implementation

---

In fact, bitmap is also a method to quickly find data by using hash idea . The bitmap represents the existence of data by two states of each bit ,0 Indicates that the data does not exist 1 Indicates that the data exists . In practical applications, it is generally used to find out whether elements exist in a particularly large amount of data .

1. Simple application of bitmap

Let's first look at the bitmap mapping of a small number of elements ： You can see in an array that there are 1 To 22 If each time we look in the array 1~22 Whether an element in the array exists or not, we need to traverse the array every time, so it is very slow , So we can use bitmap, that is to say, we can use 22 Bits to represent this 22 The existence status of numbers . Then we can look in the bitmap every time we judge whether a data exists in the array .

2. Bitmap massive data search

In real life, the data we have to deal with is often very huge , For example, we have to deal with 40 Billion of data . Search required 40 If an element exists in the data of billion, we can use the bitmap to represent .

First, let's calculate how to query 4billion data without bitmap . So let's start with a rough calculation 40 How much memory does billion data occupy .

We can see 40 Billion data has about 16 individual G We use internal sorting （ The essence of the search here is sorting , It is to sort and compare each element in the process of searching ） It's very difficult to do it because you have to do it all at once 16G Only when all the data of are loaded into memory can they be searched and compared one by one . But in reality, our memory may only be 8G perhaps 16G If this 16G It is certainly unreasonable to load all the data in memory . Then you need an external sort , But external sorting also needs to merge and sort files , Sorting is complex and time consuming . Then we can use bitmap to solve it easily .

We can see that in the way of bitmap, we only need to apply 512M Data can be achieved 40 Search of billion data .

3.STL Introduction and use of bitmap in

3.1 Introduction to bitmap ：

You can see STL The bitmap in is a specialized template that directly gives an unsigned N To represent the number of bits of the bitmap .

3.2 Use of bitmap ：

• Common usage in bitmap ：

  

  

• You can see that the elements in the lowest bit bitmap are treated as the lowest bit string when they are converted to a string

  

4. Application of bitmap

4.1. Quickly find out whether a data is in a collection

• To find data above, we use bitmap to find numbers

4.2. Sort

• In the above process of data search, the bitmap marks the data in order , So in the process of marking, we have actually completed the sorting process of data . Just set to... In the bitmap in turn 1 Bit readout of , That is the order of the data in the set .

4.3. Find the intersection of two sets 、 And set etc.

• intersection ： As for the intersection, it is easier to realize , As long as we perform bitwise and operations on each bit of the two bitmaps, the data marked in the new bitmap will be the intersection of the original two sets .
• Combine ： The new bitmap obtained by bitwise OR operation on two bitmaps is the union of the original two sets .

4.4. Disk block mark in the operating system

(1 Bar message ) Linux File system _ Moon and a half wood Jin's blog -CSDN Blog https://blog.csdn.net/weixin_45897952/article/details/123262685?spm=1001.2014.3001.5501

5. Bitmap simulation implementation

#pragma once
#include<iostream>
#include<vector>
#include<assert.h>
using namespace std;
namespace wbx
{
	template<size_t N>
	class bitset
	{
	public:
		bitset()
			:_con(N/8+1),_count(0)
		{}
		bitset& set(size_t pos, bool val = true)
		{
			if (pos >= N)
			{
				assert(true);
			}
			if (val)
			{
				_con[pos / 8] |= (1 << (pos % 8));
				_count++;
			}
			else
			{
				reset(pos);
			}
			return *this;
		}

		bitset& reset(size_t pos)
		{
			_con[pos / 8] &= (~(1 << (pos % 8)));// Place it 0
			_count--;
			return *this;
		}
		
		size_t count()
		{
			// Here, we can also use the number of digits in the bitmap corresponding to each given number to calculate count Value 
			//int bitCnttable[256] = {
			//	0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2,
			//	3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3,
			//	3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3,
			//	4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4,
			//	3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5,
			//	6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4,
			//	4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5,
			//	6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5,
			//	3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3,
			//	4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6,
			//	6, 7, 6, 7, 7, 8 };
			//_count = 0;
			//for (int i = 0; i <_con.size(); i++)
			//{
			//	_count += bitCnttable[_con[i]];
			//}

			return _count;
		}
		size_t size()
		{
			return N;
		}

		bool test(size_t pos)
		{
			int temp = _con[pos / 8] & (1 << (pos % 8));
			return bool(temp > 0 ? true : false);
		}
		//????????????? Didn't write 
		unsigned char& operator[](size_t pos)
		{// Don't know how to return a reference to a location 
			return _con[pos / 8];
		}
		string to_string()const
		{
			string ret;
			bool flag = false;
			for (int i = 0; i < _con.size(); i++)
			{
				if (i == _con.size())
				{
					flag = true;
				}
				ret += char_tostring(_con[i], flag);
			}
			return ret;
		}
		unsigned long to_ulong()const
		{
			unsigned long ret=0;
			string temp = to_string();
			int base = 0;
			for (int i = temp.size() - 1; i >= 0; i--)
			{
				ret += (temp[i] - '0')*Nsquare(base);
				base++;
			}
			return ret;
		}
	private:
		long Nsquare(int N)const
		{
			long ret = 1;
			for (int i = 0; i < N; i++)
			{
				ret *= 2;
			}
			return ret;
		}
		string char_tostring(unsigned char num,bool flag)const
			//flag Used to indicate whether the current is the last digit 
		{
			string rets;
			while (num)
			{
				unsigned long temp = num % 2;
				num /= 2;
				rets.push_back((char)(temp + '0'));
			}
			if (!flag)
			{
				while (rets.size() < 8)
				{
					rets.push_back('0');
				}
			}
			reverse(rets.begin(), rets.end());
			return rets;
		}
		vector<unsigned char> _con;
		size_t _count;
	};
}



int main()
{
	wbx::bitset<23> b;// Here we want to express 0-22 So we need to construct 23 Because it also includes 0
	int array[] = { 1, 3, 7, 4, 16, 12, 13, 19, 22, 18 };
	for (int e : array)
	{
		b.set(e);// Set every data in the array to... In the bitmap 1
	}
	if (b.test(1))
	{
		cout << "1 is in bitset" << endl;
	}
	else
	{
		cout << "1 is not in bitset" << endl;
	}
	b.reset(1);// take 1 Set the position to 0
	if (b.test(1))
	{
		cout << "1 is in bitset" << endl;
	}
	else
	{
		cout << "1 is not in bitset" << endl;
	}
	cout << b.size() << endl;// Number of bitmaps 
	cout << b.count() << endl;// The bitmap is set to 1 The number of 
	if (b.test(4))
	{
		cout << "4  The position is set to... In the bitmap 1" << endl;
	}
	else
	{
		cout << "4  The position is not set to... In the bitmap 1" << endl;
	}	
	if (b.test(10))
	{
		cout << "10  The position is set to... In the bitmap 1" << endl;
	}
	else
	{
		cout << "10  The position is not set to... In the bitmap 1" << endl;
	}
	cout << b.to_string() << endl;// Converts the setting of each bit in the bitmap to a string 
	cout << b.to_ulong() << endl;// Converts the setting of each bit in the bitmap to unsigned long type 
	return 0;
}

test result ：

If you think it's useful to see here, it's better to praise before you go ！！！