C++비트 맵 및 비트 맵 의 실현 원리

콘 셉 트
비트 맵 은 비트 맵 의 줄 임 말 입 니 다.비트 맵 이란 모든 사람 이 특정한 상 태 를 저장 하고 대규모 데이터 에 적용 되 며 이 데 이 터 는 중복 되 지 않 는 간단 한 데이터 입 니 다.일반적으로 어떤 데이터 저장 이 존재 하지 않 는 지 판단 하 는 데 쓰 인 다.
예 를 들 어 40 억 개의 중복 되 지 않 는 unsigned int 의 정 수 를 주 고 순 서 를 정 하지 않 은 다음 에 하나의 수 를 주 고 이 수가 40 억 개의 수 에 있 는 지 여 부 를 어떻게 신속하게 판단 합 니까?
데이터 양 을 보지 않 으 면 우리 가 가장 먼저 생각 하 는 것 은 바로 순서대로 처음부터 옮 겨 다 니 는 것 이다.그러나 이 데 이 터 는 매우 많 고 40 억 이 있 으 며 40 억 번 을 옮 겨 다 니 며 소모 하 는 시간 과 메모리 가 매우 많다.그러나 비트 맵 을 도입 하면 이런 대량의 데이터 검색 에 존재 하 는 문제점 을 전문 적 으로 해결 할 수 있다.이 숫자 에 소모 되 는 시간 복잡 도가 O(1)인지 찾 고 32 배의 용량 을 절약 했다(아래 설명 이 있다).다음은 비트 맵 의 원리 와 코드 실현 을 살 펴 보 겠 습 니 다.
의 원리
하나의 숫자 가 존재 하 는 지,사실 답 은 존재 하 는 지,존재 하지 않 는 지 를 찾 는 것 입 니 다.이것 은 옳 고 그 름 만 대답 하 는 문제 입 니 다.우 리 는 모두 이 진 중의 위치 로 표시 할 수 있 습 니 다.1 은 이 숫자 가 존재 하 는 것 을 나타 내 고,반대로 0 은 이 숫자 가 존재 하지 않 는 다 는 것 을 나타 냅 니 다.비트 맵 의 모든 데이터 단원 은 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트예 를 들 어 40G 의 데 이 터 는 1.3G 만 써 서 저장 합 니 다.그러나 우리 가 평소에 조작 하 는 데이터 형식 이 가장 작은 것 은 하나의 바이트 이다.우 리 는 직접 위 치 를 조작 할 수 없 기 때문에 우 리 는 비트 연산 을 통 해 데 이 터 를 조작 할 수 있다.다음은 데이터 가 비트 맵 에 어떻게 저장 되 는 지 살 펴 보 겠 습 니 다.
저희 가 여기 서 배열 을 하나 드릴 게 요.
int arr[] = {1,2,4,5,7,10,11,14,16,17,21,23,24,28,29,31}；이 데 이 터 를 저장 하기 위해 서 는 한 바이트 만 써 야 합 니 다.

설명:현재 우리 의 많은 기 계 는 모두 작은 엔 드 저장,즉 낮은 주소 로 낮은 위치 에 저장 되 어 있 습 니 다.하나의 성형 데이터 에서 첫 번 째 바이트 는 0-7 의 숫자 를 저장 하고 두 번 째 바이트 는 8-15 의 숫자 를 저장 하 며 세 번 째 바이트 는 16-23 의 숫자 를 저장 하고 네 번 째 바이트 는 24-31 의 숫자 를 저장 합 니 다.숫자 10 이 어떻게 저장 되 는 지 봅 시다.먼저 모드 32 를 통 해 나머지 를 취하 든 10 을 취하 든 4 바이트 의 10 번 째 비트 위 치 를 1 로 하면 이 숫자 가 나 타 났 음 을 나타 낸다.우리 의 기 계 는 작은 엔 드 저장 장치 이기 때문에 우리 의 모든 비트 위 치 는 오른쪽 에서 부터 계산 해 야 한다.다음 과 같다.

그 러 니까 우 리 는 대응 하 는 비트 위 치 를 1 로 만 하면 된다.그런데 저희 가 저장 할 데이터 가 크 면 요?사실은 간단 합 니 다.우 리 는 하나의 배열 을 정의 할 수 있 습 니 다.하나의 비트 맵 으로 할 수 있 습 니 다.만약 에 이 숫자 가 0-31 사이 에 있 으 면 우 리 는 0 번 아래 표 시 된 요소 에 저장 하여 조작 할 것 입 니 다.32-63 사이 에 있 으 면 1 번 아래 표 시 를 통 해 조작 할 것 입 니 다.아래 표 시 를 계산 하면 우 리 는 모 32 를 통 해 아래 표를 얻 을 수 있다.
우 리 는 비트 맵 의 원 리 를 알 게 된 후에 원 리 를 통 해 코드 로 비트 맵 을 실현 합 시다.
이루어지다
구성원 변수 와 구조 함수:비트 맵 에서 우리 의 구성원 변 수 는 하나의 배열 만 있 으 면 이 루어 집 니 다.이 배열 은 얼마나 되 고 우 리 는 얼마나 커 야 합 니까?배열 은 성형 공간 을 하나 더 열 면 32 개의 숫자 를 더 저장 할 수 있 기 때문에 우 리 는 사용자 에 게 정확 한 수 를 제공 할 수 있 습 니 다.이 수 는 데이터 양 이자 수의 최대 범위 입 니 다.우 리 는 이 모드 에서 32 를 통 해 이 배열 의 크기 를 얻 을 수 있 지만 0~31 모드 에서 32 는 0 이다.우 리 는 0 개의 공간 을 여 는 것 이 분명 적합 하지 않 기 때문에 우 리 는range/32 + 1개의 공간 크기 의 배열 을 열 어야 한다.
저장 데이터:하나의 숫자 num 을 저장 하 는 데 3 단계 가 필요 합 니 다.첫 번 째 는 이 값 에 대응 하 는 배열 아래 표 시 를 계산 해 야 합 니 다.계산 배열 아래 표 시 는 idx=num/32 입 니 다.두 번 째 단 계 는 num 이 정수 에 대응 하 는 비트 비트 비트 의 위치 bitIdx=num%32 를 계산 하 는 것 입 니 다.세 번 째 단 계 는 계 산 된 bite 위 치 를 1 로 하 는 것 이다.우리 가 전에 말 했 듯 이,위 치 를 조작 하려 면,우 리 는 위 연산 을 통 해 조작 할 수 있 으 며,먼저 1 을 왼쪽으로 이동 한 후에 정수 와 연산 하거나 연산 할 수 있다.
예 를 들 어 bitIdx=5 를 가정 하면 데 이 터 는 1001011 이다.
1.1 을 왼쪽으로 5 자리 이동==>100000
2.데이터 와 첫 번 째 단계 로 계 산 된 결 과 를 진행 하거나 연산 한다.
1001011|100000=10110011,이때 우 리 는 지 정 된 위 치 를 1 로 설정 합 니 다.
데이터 찾기:데이터 가 존재 하 는 지 여 부 를 판단 하려 면 저장 데이터 와 유사 하 며 두 개의 위치 idx 와 bitIdx 를 계산 해 야 합 니 다.그리고 이 두 위 치 를 통 해 대응 위치 가 1 인지 아 닌 지 를 판단 하고 1 이면 이 숫자 가 존재 한 다 는 것 을 나타 낸다.어떻게 판단 합 니까?우 리 는 먼저 배열 아래 에 idx 로 표 시 된 정 수 를 오른쪽으로 이동 한 다음 에 1 과 연산 을 할 수 있 습 니 다.1 이면 존재 함 을 표시 하고 그렇지 않 으 면 존재 하지 않 습 니 다.
예 를 들 어 bitIdx=5 를 가정 하면 데 이 터 는 10110011 이다.
1.데 이 터 를 오른쪽으로 5 비트 00000101 이동
2.첫 번 째 로 계 산 된 결과 와 1 을 연산 한다.
00000101&1=1,이때 이 숫자 가 존재 함 을 표시 하고 true 로 돌아 갑 니 다.
데이터 삭제:데 이 터 를 삭제 하 는 것 은 데이터 저장 작업 과 마찬가지 로 대응 하 는 bit 위 치 를 0 으로 하 는 것 입 니 다.우 리 는 먼저 1 을 왼쪽으로 bitIdx 비트 를 옮 긴 다음 에 반 을 취하 여 결 과 를 원래 데이터 와 연산 할 수 있다.
예 를 들 어 bitIdx=5 를 가정 하면 데 이 터 는 10110011 이다.
1.1 을 왼쪽으로 5 자리 옮 긴 후,역 01111
2.첫 번 째 로 계 산 된 결과 와 데 이 터 를 연산 한다.
10110011&011111=1001011,삭제 성공
코드:

class BitMap
{
public:
	//              
	BitMap(size_t range)
		:_bit(range / 32 + 1)
	{}

	void set(const size_t num)
	{
		//        
		int idx = num / 32;
		//  num             
		int bitIdx = num % 32;
		//        1
		_bit[idx] |= 1 << bitIdx;
	}

	bool find(const size_t num)
	{
		int idx = num / 32;
		int bitIdx = num % 32;
		return (_bit[idx] >> bitIdx) & 1;
	}

	void reset(const size_t num)
	{
		int idx = num / 32;
		int bitIdx = num % 32;
		_bit[idx] &= ~(1 << bitIdx);
	}
private:
	vector<int> _bit;
};

테스트 캡 처:

이상 은 C++비트 맵 과 비트 맵 의 실현 원리 에 대한 상세 한 내용 입 니 다.C+비트 맵 에 관 한 자 료 는 저희 의 다른 관련 글 을 주목 하 세 요!