bit-map概要とそのC/C++コード実装

7296 ワード

本稿では、bit-mapを紹介します.これは何のbitmap画像だと思わないでください.では、本稿で紹介するbit-mapは何ですか.ゆっくり話してください.
汽車に乗ったことがありますか.汽車の中で糞をしたいときは、トイレに行かなければなりません.おならをしてトイレに登って、上に明かりがついていることに気づいて、中に人がいることを示して、あなたは憂鬱で、しかし仕方がありません.長い間、あの人が出てきて、その明かりも消えて、トイレに行くことができます.
このランプは、コンピュータのbitの1つで、2つの状態があり、1はトイレに人がいることを示し、0はトイレに人がいないことを示しています.だから、この意味では、1つのbitはある物事の1つの状態をマークすることができて、このbitがある物事の状態とマッピングを確立した後、私たちは、1つのbitから物事の状態のmapを形成しました.

unsign charには8 bitがあることを知っています.つまり、符号のない文字はトイレの8つのピットの状態を示すことができます.次にプログラムを見てみましょう.

#include <iostream>
using namespace std;

int main(void) 
{
	unsigned char c;
	
	// 8       
	c = 0;

	// 8      
	c = 255;

	//  1 (       0 )    
	c = 128;

	//         
	c = 3;

	return 0;
}

見ましたか?ビットはピットを表し、物事の状態を表し、unsigned charは8つの物事の状態を表しています.同じように、1つのunsigned intは32の物事の状態を示しており、実際には1つのintも32の物事の状態を示すことができる.
(もちろん、ここでいう状態は二値状態です)
現在,N個の事象状態があると仮定すると,少なくとも何個のintで表す必要があるのだろうか.N/32+1であることは明らかである.100個のもの(N=100)があるとすると、少なくとも4個のint(合計128ビット)が必要となる.ちょっと言いすぎたので、直接プログラムを見ましょう.

#include <iostream>
using namespace std;

#define BIT_INT 32   // 1 int    32  
#define SHIFT 5
#define MASK 0x1f
#define N 100
int a[1 + N / BIT_INT]; //   1 + N / BIT_INT       N   

//          0  
void setAllZero()
{
	memset(a, 0, (1 + N / BIT_INT) * sizeof(int));
}

//    i  1,          
void setOne(int i)
{
	a[i >> SHIFT] |= (1 << (i & MASK));
}

//    i  1,           
void setZero(int i)
{
	a[i >> SHIFT] &= ~(1 << (i & MASK));
}

//    i   ，            
int getState(int i)
{
	return (a[i >> SHIFT] & (1 << (i & MASK))) && 1;
}

int main(void) 
{
	int bitNumber = (1 + N / BIT_INT) * BIT_INT;
	cout << bitNumber << endl;
	
	setAllZero();
	int i = 0;
	for(i = 0; i < bitNumber; i++)
	{
		cout << getState(i);
	}
	cout << endl;


	setOne(0);
	setOne(1);
	setOne(2);
	setOne(3);
	setOne(4);
	for(i = 0; i < bitNumber; i++)
	{
		cout << getState(i);
	}
	cout << endl;


	setZero(0);
	setZero(1);
	setZero(2);
	for(i = 0; i < bitNumber; i++)
	{
		cout << getState(i);
	}
	cout << endl;

	return 0;
}

結果を見てみましょう.
128 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 11111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 00011000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
案の定、結果は予想通りだった.
プログラムを見てみましょう.

#include <iostream>
#include <set>
using namespace std;


#define BIT_INT 32   // 1 int    32  
#define SHIFT 5
#define MASK 0x1f
#define N 100
int a[1 + N / BIT_INT]; //   1 + N / BIT_INT       N   


//       
unsigned  int getRandom()
{
	return rand();
}

//          0  
void setAllZero()
{
	memset(a, 0, (1 + N / BIT_INT) * sizeof(int));
}

//    i  1,          
void setOne(int i)
{
	a[i >> SHIFT] |= (1 << (i & MASK));
}

//    i  1,           
void setZero(int i)
{
	a[i >> SHIFT] &= ~(1 << (i & MASK));
}

//    i   ，            
int getState(int i)
{
	return (a[i >> SHIFT] & (1 << (i & MASK))) && 1;
}

int main(void) 
{
	int r = N;
	int size = 40; //    40   (  )，    [0, N-1]     

	//   40        ,    , s        ，       ，           
	set<int> s;
	while(size != s.size())
	{
		s.insert(getRandom() % r);
	}

	//           ，    
	setAllZero();

	set<int>::iterator it;
	for(it = s.begin(); it != s.end(); it++)
	{
		setOne(*it); //    *it       *it    ，  *it       ，      *it    1
		cout << *it << " ";
	}
	cout << endl;

	int i = 0;
	int bitNumber = (1 + N / BIT_INT) * BIT_INT;
	for(i = 0; i < bitNumber; i++)
	{
		cout << i << "        :--->" << getState(i) << endl; //       
	}
	cout << endl;

	return 0;
}

結果:
0 2 3 4 5 11 12 16 18 21 22 22 24 27 33 34 36 38 41 42 45 47 53 58 61 62 64 69 71 73 78 81 82 92 94 95 99 0対応ピット状態:-----1対応ピット状態:-----0 2対応ピット状態:-----1 3対応ピット状態:-----1 4対応ピット状態:-----1 5対応ピット状態:-----1 6対応ピット状態:-----1 6対応ピット状態:-----0 7対応ピット状態ピット状態:----->0 8対応ピット状態:----->0 9対応ピット状態:----->0 10対応ピット状態:----->0 11対応ピット状態:----->1 12対応ピット状態:----->1 13対応ピット状態:----->0 14対応ピット状態:----->0 15対応ピット状態:----->0 16対応ピット状態:----->1 17対応ピット状態:----->018対応ピット位置状態:----->1 19対応ピット位置状態:----->0 20対応ピット位置状態:----->0 21対応ピット位置状態:----->1 22対応ピット位置状態:----->1 23対応ピット位置状態:----->0 24対応ピット位置状態:----->1 25対応ピット位置状態:----->0 26対応ピット位置状態:----->1 27対応ピット位置状態:----->1 28対応ピット位置状態:----->0 29対応ピット位置状態:----->0 30対応ピット位置状態:----->0 31対応ピット位置状態:----->0 32対応ピット位置状態:----->0 33対応ピット位置状態:----->1 34対応ピット位置状態:----->1 35対応ピット位置状態:----->1 36対応ピット位置状態:----->1 37対応ピット位置状態:----->0 38対応ピット位置状態:----->1 39対応するピット状態は、----->0 40対応のピット状態は、----->0 41対応のピット状態は、----->1 42対応のピット状態は、----->1 43対応のピット状態は、----->0 44対応のピット状態は、----->0 45対応のピット状態は、----->1 46対応のピット状態は、----->0 47対応のピット状態は、----->1 48対応のピット状態は、----->0 49対応のピット状態である状態:----->0 50対応ピット位置状態:----->0 51対応ピット位置状態:----->0 52対応ピット位置状態:----->0 53対応ピット位置状態:----->1 54対応ピット位置状態:----->0 55対応ピット位置状態:----->0 56対応ピット位置状態:----->0 57対応ピット位置状態:----->0 58対応ピット位置状態:----->1 59対応ピット位置状態:----->0 60対対応するピット状態は、----->0 61対応のピット状態は、----->1 62対応のピット状態は、----->1 63対応のピット状態は、----->0 64対応のピット状態は、----->1 65対応のピット状態は、----->0 66対応のピット状態は、----->0 67対応のピット状態は、----->1 68対応のピット状態は、----->0 69対応のピット状態は、----->1 70対応のピット状態であるは、----->0 71に対応するピット状態は、----->1 72に対応するピット状態は、----->0 73に対応するピット状態は、----->1 74に対応するピット状態は、----->0 75に対応するピット状態は、----->0 76に対応するピット状態は、----->0 77に対応するピット状態は、----->0 78に対応するピット状態は、----->1 79に対応するピット状態は、----->0 80に対応するピット状態は、----->0 81に対応するのピット状態は、----->1 82に対応するピット状態は、----->1 83に対応するピット状態は、----->0 84に対応するピット状態は、----->0 85に対応するピット状態は、----->0 86に対応するピット状態は、----->0 87に対応するピット状態は、----->0 88に対応するピット状態は、----->0 89に対応するピット状態は、----->0 90に対応するピット状態は、----->0 91に対応するピット状態は、----->1 92対応ピット状態:----->1 93対応ピット状態:----->0 94対応ピット状態:----->1 95対応ピット状態:----->1 96対応ピット状態:----->0 97対応ピット状態:----->0 98対応ピット状態:----->0 99対応ピット状態:----->1 100対応ピット状態:----->0 101対応ピット状態:----->0 102対応のピット状態は、----->0 103対応のピット状態は、----->0 104対応のピット状態は、----->0 105対応のピット状態は、----->0 106対応のピット状態は、----->0 107対応のピット状態は、----->0 108対応のピット状態は、----->0 109対応のピット状態は、----->0 110対応のピット状態は、----->0 111対応のピット状態は、----->0 112対応のピット状態である状態:----->0 113対応ピット状態:----->0 114対応ピット状態:----->0 115対応ピット状態:----->0 116対応ピット状態:----->0 117対応ピット状態:----->0 118対応ピット状態:----->0 119対応ピット状態:----->0 120対応ピット状態:----->0 121対応ピット状態:----->0 122対応ピット状態:----->0 123に対応するピット状態は、----->0 124に対応するピット状態は、----->0 125に対応するピット状態は、----->0 126に対応するピット状態は、----->0 127に対応するピット状態は、----->0は現在bit-mapをクリアすべきである、bit-mapとは、実际には1つのbitでmapを1つの物事から除去する状態(二値状態)である.bit-mapのメリットは、スペースを節約することです.
実際、bit-mapはビッグデータ処理でよく使われ、いくつかの筆記試験の面接問題はよく試験され、その後、続々と紹介されます.

SpringMVC ExcelファイルをMySQLにインポート

C++学習——クラスの継承