(c++) 비트마스크(bitmask) 정리

비트마스크(bitmask)

 

 

0, 1로 이루어진 이진수를 자료 구조 형태로 사용하는 기법을 비트마스크라 한다.

 

비트 연산자를 이용한다면 일반 계산보다 빠른 연산이 가능하다.

 

AND, OR, XOR로 특정 비트를 변경, 삭제, 추가가 가능하고,

쉬프트 연산을 통해서 곱셈, 나눗셈을 빠르게 연산가능하다.

 

 

정수 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

 

 

 

비트마스크는  집합에 사용되는 경우가 많은데 

{1, 2, 4} 배열일 경우 $$ 2^{1} + 2^{2} + 2^{4} = 1\;0110 $$

원소 i는 2 ^ i 번째 비트가 1로 되어있다는 것으로 사용한다.

 

 

집합에서 사용

 

 

집합에 원소 추가

 

추가할 원소 자리까지 쉬프트로 이동한 다음 1과 or 연산을 해주면 

해당 자리가 0, 1 즉 어떤 경우에도 1로 바꾼다.

S[i] |= (1 << i);

 

 

집합 원소 포함 여부 확인

 

해당 자리가 1로 채워져 있는지 확인

if(S[i] & (1 << i)) // 1 == true, 2 == false

 

 

원소 삭제

 

해당 자리를 빼주어도 되지만

해당 자리가 비어있을 경우 오류가 나기에

not 연산을 해주고 and 연산을 해주면 해당 자리가 존재하지 않더라도 해결된다.

S[i] -= (1 << i); // 빼주기 S[i]가 존재하는 경우만
S[i] &= ~(1 << i); // S[i]가 존재하지 않는 경우 처리 가능

 

 

원소 토글

 

해당 비트가 1이면 0으로, 0이면 1로 바꾸는 것을 토글(toggle)

XOR 연산을 통해서 해준다.

XOR은 둘의 비트가 다를 경우만 참

S[i] ^= (1 << i);