비트 마스크

Bit Mask

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

N비트 정수는 0부터 N-1까지의 정수 원소를 가질 수 있는 집합이 된다.

원소 i가 집합에 속해 있는지의 여부는 2^i 을 나타내는 비트가 1인지 확인하는 여부로 나타낸다.

꽉 찬 집합 - (원소 20개 가정)

---

int fullSet = (1<<20) - 1;

• 1«20 : 2진수로 1 뒤에 20개의 0이 있는 정수
• (1«20) - 1 : 20개의 비트가 1인 2진수

원소 추가

---

set |= (1<<element);

• 원소번호 : 0 < element < 20
• 1«element : 1을 왼쪽으로 element비트 shift하면 element번 비트만 1인 정수
• set과 (1«element)를 OR하면 집합에서 해당 비트는 1로 변한다.

원소의 포함 여부 확인

---

//맞는 코드
if(set & (1<<element)){
  System.out.println("found");
}


//틀린 코드
if(set & (1<<element) == 1){
  System.out.println("found");
}

• AND 연산 결과 0 또는 1«element 값이 나오게 된다.
• AND 연산 결과가 1«element인 경우 : element가 0이 아니라면 1«element가 1은 아니다. 즉 AND 연산 결과 == 1은 틀린 코드이다.

원소의 삭제

---

set &= ~(1<<element);

• ~(1«element) : element번 비트만 0이 되고 나머지는 1이 된다.
• AND 연산 후 : 나머지 비트는 유지되고 element번 비트만 0이 된다.

원소의 토글 ( on <-> off )

---

set ^= (1<<element);

두 집합의 연산

---

//합집합
int add = (a | b);

//교집합
int intersection = (a & b);

//차집합
int removed = (a & ~b);

//두 집합 중 하나에만 포함된 원소들의 집합
int toggled = (a ^ b);