비트 마스크

비트 마스크란 0과 1의 bit, 즉 이진수를 활용한 기법이다. 배열을 이용하는 것 보다 훨씬 적은 메모리 공간을 차지하기때문에 문제에서 종종 사용된다.

두 정수 a, b를 비트별로 AND 연산	a & b
두 정수 a, b를 비트별로 OR 연산	a | b
두 정수 a, b를 비트별로 XOR 연산	a ^ b
정수 a를 비트별 NOT 연산	~a
정수 a를 왼쪽으로 b비트 쉬프트	a << b
정수 a를 오른쪽으로 b비트 쉬프트	a >> b

 

아래 코드에 비트 마스크를 사용하는데 유용한 여러 기법들이 있다.

---

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Algorithm/%EB%B9%84%ED%8A%B8%EB%A7%88%EC%8A%A4%ED%81%AC.cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <intrin.h> //__popcnt 포함 헤더
using namespace std;

//n개의 1로 꽉찬 비트 반환
int fullBit(int n)
{
	return (1 << n) - 1;
}

//bit의 n번째 위치에 원소를 추가
int insertBit(int bit, int n)
{
	bit |= (1 << n);
	return bit;
}

//bit의 n번째 위치에 원소가 포함되어있는가
bool isContain(int bit, int n)
{
	bool res = (bit & (1 << n));
	return res;
}

//bit의 n번째 위치의 원소를 삭제
int removeBit(int bit, int n)
{
	//bit -= (1<<n)은 bit에 n번째 원소가 없는경우 오류가 발생
	bit &= ~(1 << n);
	return bit;
}

//bit의 n번째 원소의 값 변경( 1이면 0, 0이면 1로)
int toggleBit(int bit, int n)
{
	bit ^= (1 << n);
	return bit;
}

int calculate(int a, int b)
{
	int added = (a | b); //a와 b의 합집합
	int intersection = (a & b); //a와 b의 교집합
	int removed = (a & ~b); //a에서 b를 뺀 차집합
	int toggle = (a ^ b); //a와 b중 하나만 포함된 원소
	return added;
}

//x에 포함된 원소의 수
int bitCount(int x)
{
	if (x == 0) return x;
	return x % 2 + bitCount(x / 2);

	/*	
		간편한 방법
		return __popcnt(x);
	*/

	/*	원시적인 방법
		int cnt = 0;
		for(int i=0; i < size; i++){
			if(x & (1<<i)) cnt++;
		}
		return cnt;
	*/
}

//bit의 첫번째 원소 위치
int firstBit(int bit)
{
	return (bit & -bit);
}

//모든 부분집합 순회하기
void circuit(int bit)
{
	for (int subset = bit; subset > 0; subset = ((subset - 1) & bit)) {
		//
	}
}