티스토리 뷰

coding test

비트 마스크

풀풀풀 아풀 2018. 6. 1. 14:28

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);


'coding test' 카테고리의 다른 글

비트 마스크  (0) 2018.06.01
댓글
댓글쓰기 폼