[Algorithm] 비트마스킹(Bit Masking)

 

비트마스킹(Bit Masking) 이란?

 

  1.  비트란 ?

 

    -  데이터를 나타내는 최소 단위

 

    -  모든 데이터는 0과 1의 조합으로 구성되고, 0 또는 1이 하나의 비트가 됨

 

    -  1개의 비트는 2가지 상태를 나타낼 수 있다 -> n 개의 비트로는 2 ^ n 가지의 상태를 나타낼 수 있다.

 

 

  2.  비트마스킹이란 ?

 

    -  컴퓨터가 내부적으로 모든 자료를 이진수로 표현하는 특성을 이용해 정수의 이진수 표현을 자료구조로 쓰는 기법

 

    -  비트 마스크를 이용하면, 더 빠른 수행 시간 + 더 간결한 코드 + 더 적은 메모리 사용 효과를 얻을 수 있다.

 

    -  집합의 배열을 인덱스로 표현할 수 있다.

 

 

비트 연산자(논리 연산자)

 

연산자	표기	역할	예시
AND	a & b	a 와 b 두 비트 모두 1이면 1, 아니면 0	a = 4 = 100(2) b = 7 = 111(2) a & b = 100(2) = 4
OR	a | b	a 와 b 두 비트 중 하나라도 1이면 0	a = 2 = 010(2) b = 5 = 101(2) a | b = 111(2) = 7
XOR	a ^ b	a와 b 두 비트가 서로 다르다면 1, 같으면 0	a = 3 = 011(2) b = 5 = 101(2) a ^ b = 110(2) = 6
NOT	~ a	a의 모든 비트에 NOT 연산 0이면 1, 1이면 0	a = 3 = 011(2) ~ a = 100(2) = 4
Left-shift	a << b	a 를 b 비트 만큼 왼쪽으로 시프트	a = 1 = 001(2) a << 2 = 100(2) = 4
Right-shift	a >> b	a 를 b 비트 만큼 오른쪽으로 시프트	a = 4 = 100(2) a >> 2 = 011(2) = 1

 

 

집합의 표현

 

  1.  집합의 표현

 

    (1)  원소의 개수가 N 인 집합이 있을 때

 

      -  각각의 원소를 0번부터 ~ (N-1)번까지 번호를 부여하고

 

      -  번호에 해당하는 비트가 1이면 원소가 포함, 0이면 원소가 불포함 으로 하여 집합을 비트를 이용해 표현 가능

 

    (2)  예시

 

      -  {A, B, C, D, E, F, G} 라는 집합의 원소 = 7개 -> 7개의 비트로 집합 표현 가능

 

      -  각 원소마다, 비트를 하나씩 대응시켜 원소가 존재한다면 -> 1, 존재하지 않는다면 -> 0 으로 표현

 

      -  {A, B, C} 부분집합은 112 = 1110000(2) 로, {A} 부분집합은 64 = 1000000(2) 로 표현한다.

 

 

 

  2.  원소 추가

 

    (1)  원소 추가 과정

 

      -  현재 상태 current 에 p 번 원소를 추가하는 상황에서, 

 

      -  현재 상태 current 에서 p 번 비트를 1로 바꿔줘야 한다.

 

      -  OR 연산 활용

 

      -  a | b 비트 연산자를 활용해 해결 가능

 

      -  1 << p : p 번 비트만 1, 나머지 비트는 0으로 만들고

 

     ->  | 연산을 통해 current 의 p 번 비트는 1로 바뀌고, 나머지 비트는 원래 상태 유지

 

current = current | (1 << p)

 

    (2)  예시

 

      -  현재 이진수 current = 10101 일 때, i = 3 번째 비트 값을 1로 변경하고자 할 때,

 

      -  10101 을 변경한 후에는 -> 11101 이 나와야 한다.

 

      1)  1 << 3 적용 : 1000

 

      2)  10101 | 01000 = 11101

 

 

 

  3.  원소 삭제

 

    (1)  원소 삭제 과정

 

      -  현재 상태 current 에서 p 번 원소를 삭제하는 상황에서,

 

      -  p 번 비트를 0 으로 바꿔줘야 함

 

      -  AND 연산과 NOT 연산 활용

 

      1)  1 << p : p번 비트만 1로, 나머지 비트는 0 으로 만들고

 

      ->  ~ 연산을 통해 p 번 비트만 0, 나머지 비트는 1로 만들고

 

      ->  & 연산을 통해 p 번 비트만 0 으로 바꾸고, 나머지는 현재 상태 current 와 동일하게 유지

 

      2)  ~1 << p : p 번 비트만 0 으로, 나머지 비트는 1로 만들고

 

      ->  & 연산을 통해 p 번 비트만 0 으로 바꾸고, 나머지는 현재 상태 current 와 동일하게 유지

 

current = current & (~1 << p)

current = current & ~(1 << p)

 

    (2)  예시

 

      -  현재 이진수 current = 11101 일 때, i = 3 번째 비트 값을 0으로 변경하고자 할 때,

 

      -  11101 을 변경한 후에는 -> 10101 이 나와야 한다.

 

      1)  1 << 3 적용 : 1000 -> 01000

 

      2)  ~ 1 << 3 적용 : 10111

 

      3)  11101 & 10111 적용 : 10101

 

 

 

  4.  원소 조회

 

    (1)  원소 조회 과정

 

      -  현재 이진수 current = 10101 일 때, p 번째 비트가 무슨 값인지 알고자 할 때,

 

      -  AND 연산 활용

 

       -  1 << p : 1 번 비트만 1로, 나머지 비트는 0 으로 만들고

 

      ->  & 연산을 통해  p 번째 비트 값이 무엇인지 파악

 

current & (1 << p)

 

    (2)  예시

 

      -  아래와 같이, 결과값이 0 이 나오면 -> p 번째 비트 값이 0 임을 알 수 있다.

 

      -  이때, 반대로 0이 아니면 무조건 1인 것이다.

 

current = 10101

3번째 비트 값 : 10101 & (1 << 3) = 10101 & 01000 = 0

4번째 비트 값 : 10101 & (1 << 4) = 10101 & 10000 = 10000

 

 

 

  5.  원소 토글

 

    (1)  원소 토글

 

      -  p 번 비트가 1 이면 -> 0 / 0이면 -> 1 로 바꾸는 연산

 

    (2)  원소 토글 과정

 

      -  현재 상태 current 에서 p 번 원소가 있다면 삭제하고, 없다면 추가하는 상황에서,

 

      -  1 << p : p 번 비트만 1, 나머지 비트는 0 으로 만든다.

 

      -  current 의 나머지 비트들은, 0 과 XOR 연산 진행 : 0 이면 0, 1 이면 1 로 -> 현재 상태 유지

 

      -  p 번 비트는, 1과 XOR 연산 진행 : 1 이면 0, 0 이면 1로 토글됨

 

 

 

  6.  집합 연산(합집합)

 

 

    (1)  a | b

 

      -  두 집합 A, B 에 어느 하나에 존재하는 원소들의 비트는 모두 1로, 두 집합에 모두 존재하지 않는 원소들만 비트가 0 으로 

 

    (2)  a & b

 

       -  두 집합 A, B 모두 존재하는 원소들의 비트 : 1과 1에 대해 AND 연산 수행 - >1 

 

       -  나머지 0

 

    (3)  a & ~ b

 

       -  집합 A와 집합 B의 여집합과 & 연산을 하므로, A - B 인 집합이 결과가 된다.

 

    (4)  a ^ b

 

       -  집합 A 와 집합 B 둘 중 하나에만 포함된 원소들만 1 로 살아남게 됨

 

1. a 와 b 의 합집합
   a | b

2. a 와 b 의 교집합
   a & b

3. a 와 b 의 차집합(a에서 b를 뺀 차집합)
   a & ~b

4. a 와 b 중 하나에만 포함된 원소들의 집합
   a ^ b

 

 

  7.  집합의 크기 구하기

 

    -  집합의 크기를 구하려면, 현재 1로 켜져있는 비트 수를 Count 한다.

 

    -  모든 비트를 순회해야 하므로 재귀적으로 구현 가능

 

    1)  x % 2 : 마지막 비트를 얻음

 

    2)  x / 2 : 마지막 비트 삭제

 

    ->  모든 비트를 재귀적으로 순회

 

int bitCount(int x) {
    if (x == 0) return 0;
    return x % 2 + bitCount(x/2);
}

 

 

  8.  모든 부분 집합 순회하기

 

    -  어떤 집합의 모든 부분 집합을 순회하는 과정 구현 가능

 

for (int subSet = set; subSet; subSet = (subSet - 1) & set) {
    // subSet은 set의 부분집합 중 하나
}

 

    (1)  예시

 

      -  {A, B, D} 집합의 모든 부분 집합을 순회하고자 할 때,

 

      -  {A, B, D} 의 부분 집합은 공집합 제외 {A}, {B}, {D}, {A, B}, {A, D}, {B, D}, {A, B, D}

 

      -  각 부분 집합을 비트로 표현하면 아래와 같다.

 

 

{A}	1000
{B}	0100
{D}	0001
{A, B}	1100
{A, D}	1001
{B, D}	0101
{A, B, D}	1101

 

      -  set = 1101(2) = {A, B, D} 에 대해 위의 부분 집합 순회 과정을 처리하면

 

subSet	(subSet - 1)	(subSet - 1) & set
1101(2)  // {A, B, D}	1100(2)	1100(2)
1100(2)  // {A, B}	1011(2)	1001(2)
1001(2)  // {A, D}	1000(2)	1000(2)
1000(2)  // {A}	0111(2)	0101(2)
0101(2)  // {B, D}	0100(2)	0100(2)
0100(2)  // {B}	0011(2)	0001(2)
0001(2)  // {D}	0000(2)	0000(2) // 종료

 

    - (subSet - 1) & set 을 통해 for 문을 돌면서 모든 부분 집합을 순회할 수 있다 ! 

 

 

 

참고자료

 

  -  참고1

  -  참고2