비트 마스크(Bit Mask)

이번에 정리해 볼 내용은 비트 마스크이다.

 

비트(Bit)

컴퓨터에서 사용되는 데이터의 최소 단위. 이진숫자.

일반적으로 0과1, true와 false, on과 off 의 상태를 나타낼 수 있다.

<비트 연산>

1.  AND 연산( & )
   연산하는 두 비트 모두 1일 때, 1을 반환한다.
   
   111 & 101 = 101
   
   
2.  OR 연산( | )
   연산하는 두 비트 중 하나라도 1일 때, 1을 반환한다.
   
   100 & 010 = 110
   
   
   
3.  XOR 연산(^)
   연산하는 두 비트가 서로 다르면 1을 반환한다. 
   
   101 ^ 010 =111
   
   
   
4.  NOT 연산(~)
   비트 값을 반전하여 반환한다.
   
   ~010 = 101
   
   
5.  시프트(Shift)연산(<<,>>)
   해당 방향으로 비트를 옮긴다.  
   
   110 << 2 == 11000      :      6 -> 24 ( == 6*2*2)
   1000 >>3 == 1       :       8 -> 1 (== ((8/2)/2)/2)  

    

비트 마스크(Bit Mask)

정수의 이진수 표현을 자료구조로 사용한 기법. 비트의 형태를 활용한다.

집합을 구현하여 원소 k 가 집합에 속한 여부를 2^k 자리의 비트상태로 나타낼 수 있다. 

비트마스크의 사용 이점

- 배열을 사용하는 것이 편리하지만, 집합을 배열의 인덱스로 표현 가능하다.

- 작은 메모리 사용

- 간결한 코드

 

비트마스크  연산

• 삽입 

집합 A에 원소 X를 삽입    :    A |= ( 1<<X )

 

• 삭제

집합 A에 원소 X를 삭제   :   A &= ~( 1<<X )

 

• 검색  

집합 A에 원소 X의 존재 확인   :   A & ( 1<<X )   

   존재한다면 1을 반환하고 존재하지 않는다면 0을 반환한다.

 

 

 

 

 

 

위의 내용을 이용해서 풀수있는 문제(백준13701번_중복제거)

https://www.acmicpc.net/problem/13701

13701번: 중복 제거

비트마스크를 사용해본적은 처음인 문제였다. 메모리제한이 상당히 작아서 놀랐던 문제. 가볍게 봤다가 비트마스크라는 걸 공부하게된 좋은 문제라고 생각이 들었다. 숫자를 하나의 비트라고 생각하는게 포인트였는데 그걸 생각해내는게 참 어려웠다.