Bit Mask

 

예전에 알고리즘 스터디를 할 때, 비트마스크 개념에 대해 배웠는데 너무 오래전 기억이라 다시 문제를 풀려니 기억나지 않아서

제대로 정리를 하고자 한다.

---

비트마스크 란?

- 용어 그대로 bit(0, 1) 에 관련된 기법 / 정수의 이진수 표현을 활용한 기법

- 0 : 꺼져있다 / 1 : 켜져있다

 

활용 예제 ?

- 비트마스크를 이용한 집합의 구현

 

우리는 길이가 5인 집합 { 0, 1, 2, 3, 4 } 가 존재한다고 가정해본다.

여기서 몇가지 요소를 뽑아 어떤 요소를 선택했는 지 표현할 수 있다.

즉, 집합의 어떤 요소를 구성하고 있는지를 나타내는 부분집합을 어떻게 표현할 수 있는가?

 

{ 0, 1, 2, 3, 4 } => 11111
{ 1, 2, 3, 4 } => 11110
{ 1, 2, 4 } => 10110
{ 2, 4 } => 10100
{ 1 } => 00010
...

= 이처럼 비트마스크를 통해 효율적으로 구할 수 있다 !

출처: https://mygumi.tistory.com/361 [마이구미의 HelloWorld]

 

연산?

- AND 연산(&) : 대응하는 두 비트가 모두 1일 때, 1 반환

- OR 연산(|) : 대응하는 두 비트가 서로 다르면 1 반환

- NOT 연산(~) : 비트의 값을 반전 ex) ~1001 → 0110

- XOR 연산(^) : 대응하는 두 비트가 서로 다르면 1을 반환

- 시프트(Shift) 연산(>>, <<) : 왼쪽 또는 오른쪽으로 비트를 옮김

• A >> B (A 를 오른쪽으로 B비트만큼 이동)
• A << B (A 를 왼쪽으로 B비트만큼 이동)

# 왼쪽 시프트 → A * 2^B
00001010 << 2 = 101000
# 오른쪽 시프트 → A / 2^B
00001010 >> 2 = 000010 

 

A라는 집합에서 특정 n 을 추가 할때

A | (1 << n)

A라는 집합에서 특정 n 을 확인 할때

A & (1 << n) 

값이 있다면 (1<<n) 이 나온다. 즉 ,  A & (1 << n) == 1

A라는 집합에서 특정 n 을 제거 할때

A & ~(1 << n)

A라는 집합에서 각 값을 토글 할때 

(토글(toggle)의 의미는 해당 비트가 꺼져있으면 키고, 켜져있으면 끄는 것을 의미)

A ^ (1 << n)

출처: https://ikso2000.tistory.com/75 [띠그랭 ]

 

집합의 모든 부분집합 순회

// N은 원소개수
for(int bit = 1 ; bit < (1<<N) ; bit++) {
...
}