Algorithm/Theory

비트 마스크(Bit Mask)

NAWIN 2019. 12. 28. 01:40
반응형

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

 

비트(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번: 중복 제거

문제: N개의 정수 A1, A2, ..., AN 을 읽고, 이들 중에서 반복되는 수를 제외하고 남은 N'개의 수 B1, B2, ..., BN’ 을 입력된 순서대로 출력하시오. 이때, 0 ≤ Ai < 225 = 33554432, i=1,2,…,N. 입력의 개수 N은 1 이상 500만 이하이다.

www.acmicpc.net

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

반응형