비트마스크 (BitMask)

🔹 비트마스크(BitMask)란 ?

• 컴퓨터는 내부적으로 모든 자료를 이진수(비트)로 처리한다.
• 이런 컴퓨터의 연산 방식을 하여 이진수의 비트 단위로 데이터를 처리하는 기법이다.

 

🔹 비트(Bit)란 ?

• 비트는 이진수(0과 1로 구성된 수)를 나타내는 말로 컴퓨터에서 사용하는 데이터의 최소 단위이다.
• 비트는 1과 0의 값을 가질 수 있고, true(1) 또는 false(0)라는 상태를 나타낼 수도 있다.
• 우리가 사용하는 10진수는 0과 1로 구성된 비트(이진수)로 표현이 가능하다.

 

🔹 왜 비트마스크를 사용할까?

• 다른 자료 구조에 비해 수행시간이 빠르다.
  • 대부분의 연산이 O(1)의 시간복잡도를 가진다.
  • 특정 원소의 존재 여부를 판단할 때, 선형 탐색할 필요 없이 AND 연산 결과가 0이 아닌지 체크하여 검사한다.
• 비트 연산자를 사용하여 코드가 더 간결해진다.
  • 집합을 배열의 인덱스로 표현할 수 있다.
• 비트마스크를 사용하여 더 작은 메모리를 사용할 수 있다.
  • boolean type으로 배열의 방문 체크를 하는 경우 1byte를 사용하지만, 비트마스킹을 사용하면 1bit로 방문 체크함으로써 메모리를 줄일 수 있다.
• DP, 순열 등 배열 활용만으로 해결할 수 없는 문제

 

🔹 비트 연산

◽ AND 연산 : A & B

A = 27, B = 83인 경우, A와 B를 이진수로 표현하면 아래와 같다.
A = 11011, B = 1010011

AND 연산 적용
   0 0 1 1 0 1 1
& 1 0 1 0 0 1 1
---------------------
   0 0 1 0 0 1 1

출력 : A & B = 19

• AND 연산의 경우 각 자릿수를 비교하여 두 비트 모두 1인 경우 1을 반환한다.
• 예제의 A와 B는 자릿수가 다르므로 이를 맞춰주기 위해 A의 앞에 0을 추가하여 B와 자릿수를 맞춰준다.

 

◽ OR 연산 : A | B

A = 27, B = 83인 경우, A와 B를 이진수로 표현하면 아래와 같다.
A = 11011, B = 1010011

OR 연산 적용
   0 0 1 1 0 1 1
|  1 0 1 0 0 1 1
---------------------
   1 0 1 1 0 1 1

출력 : A | B = 91

• OR 연산은 두 비트 중 한 개라도 1인 경우 1을 반환한다.

 

◽ XOR 연산 : A ^ B

A = 27, B = 83인 경우, A와 B를 이진수로 표현하면 아래와 같다.
A = 11011, B = 1010011

XOR 연산 적용
    0 0 1 1 0 1 1
^  1 0 1 0 0 1 1
---------------------
    1 0 0 1 0 0 0

출력 : A ^ B = 72

• XOR 연산은 두 비트가 서로 다를 경우 1을 반환한다.

 

◽ NOT 연산 : ~ A (보수)

A = 83인 경우, A를 이진수로 표현하면 아래와 같다.
A = 01010011

NOT 연산 적용
8 비트 ~A : 10101100
32비트 ~A : 11111111111111111111111110101100

출력 : 172(Unsigned), -84(Signed)

• NOT 연산의 경우 사용하는 데이터의 자료형에 따라 결과가 달라질 수 있다. 주로 사용되는 데이터의 자료형은 signed와 unsigned이 있다.
• NOT 연산은 이진수의 각 비트를 반전시키는 연산이다. 각 비트를 0은 1로, 1은 0으로 바꾼다.

 

◽ Left Shift : A << B

A << B
A를 B만큼 왼쪽으로 밀어준다는 의미의 식이다.
밀어준 만큼 동시에 0을 추가해 준다.

1 << 0 : 1
1 << 1 : 2 (10)
1 << 2 : 4 (100)
1 << 3 : 8 (1000)
1 << 4 : 16 (10000)
3 << 3 : 24 (11000)
5 << 10 : 5120 (1010000000000)

• A << B 식은 A * 2의 B 제곱과 같다.

 

◽ Right Shift : A >> B

A >> B
A를 B만큼 오른쪽으로 밀어준다는 의미의 식이다.
밀어준 만큼 동시에 0을 추가해 준다.

1 >> 0 : 1
1 >> 1 : 0 (0)
10 >> 1 : 5 (101)
10 >> 2 : 2 (10)
10 >> 3 : 1 (1)
30 >> 1 : 15 (1111)
1024 >> 10 : 1 (1)

• A >> B 식은 A / 2의 B 제곱과 같다.

 

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

비트마스크를 이용한 집합 구현은 가장 대표적이고, 자주 쓰이는 방법이다.

하나의 bit가 하나의 데이터 상태를 의미한다. bit가 1이면 해당 원소가 집합에 포함되어 있다는 의미이고, 0이면 포함되어 있지 않다는 의미이다.

따라서 N비트는 N개의 원소를 갖는 집합의 부분 집합들을 모두 표현할 수 있다.

 

◽ 공집합과 꽉 찬 집합 구하기

int A = 0;
A = (1 << 10) - 1; // 1023

• 기본적으로 공집합은 bit가 모두 꺼진 상황이기 때문에 상수 0이 공집합을 표현한다.
• 반대로 꽉 찬 집합은 bit가 모두 켜진 상황이기 때문에 1111111111의 값으로 표현한다

 

◽ 원소 추가

A |= (1 << k)

• A 집합에 특정 원소를 추가하는 방법이다.
• 원소에 해당하는 bit만 켜야 하기 때문에 해당 bit를 항상 1로 만들기 위해 OR 연산을 이용한다.

 

◽ 원소 삭제

A &= ~(1 << k)

• A 집합에 포함된 특정 원소를 삭제하는 방법이다.
• A에 k번째 원소의 포함 여부와 상관없이 해당 bit를 끄기 위해 AND 연산을 이용한다,
  • 1 << k : k번째 위치의 비트를 1로 설정
  • ~(1 << k) : k번째 위치의 비트를 0으로 만듦 (반전)
  • A & ~(1 << k) : A 집합에 담긴 k번째 비트를 0으로 설정

 

◽ 원소의 포함 여부 확인

if ((A & (1 << k)) == (1 << k))

• A 집합에 특정 원소가 포함되어 있는지 확인하는 방법이다.
• k번째 원소가 포함되어 있는지 확인하고 싶다면, k번째 비트가 켜져 있는지 확인하면 된다.
  • A & (1 << k) : 집합 A에서 k번째 위치의 비트가 1인지 확인
  • (A & (1 << k)) == (1 << k) : AND 연산의 결과가 1 << k과 같은지 비교

 

◽ 원소의 토글

A ^= (1 << k)

• A 집합에 해당 원소가 빠져있는 경우 추가하고, 들어있는 경우 삭제하는 방법이다.
• XOR 연산을 이용한다.

 

◽ 두 집합에 대해 연산하기

A | B           // A와 B의 합집합
A & B         // A와 B의 교집합
A & (~B)    // A에서 B를 뺀 차집합
A ^ B         // A와 B 중 하나에만 포함된 원소들의 집합

• 두 집합을 A와 B라고 한다면, 비트 연산자들을 통해 A와 B의 합집합, 교집합, 차집합 등을 구할 수 있다.

◽ 집합의 크기 구하기

int bitCount(int A) {
       if (A == 0) return 0;
       return A % 2 + bitCount(A / 2);
|

//  내장 명령어
Integer.bitCount(A)

• 집합에 포함된 원소의 크기를 구한다면 A에 켜진 bit 수를 구하면 된다.
• 직접 모든 비트를 확인하면서 개수를 체크할 수 있고, 내장 명령어를 이용할 수도 있다.
  • if (A == 0) return 0 : A가 0이면 이진수로 '0'이기 때문에 1의 개수는 0개이다.
  • return A % 2 + bitCount(A / 2)
    • A % 2 : A의 가장 오른쪽 비트가 1인지 0인지 확인
    • A / 2 : A를 오른쪽으로 1비트 이동한 것과 같음
    • 이를 재귀적으로 모든 비트가 처리될 때까지 반복

 

◽ 최소 원소 찾기

int first = A & (-A)

• 집합에 포함된 가장 작은 원소를 찾는 방법이다.
• 즉, 켜져 있는 bit 중에서 가장 오른쪽에 있는 bit를 찾는 것이다.
• 비트마스크뿐만 아니라 펜윅 트리(Fenwick Tree)에서도 사용되는 기법이다.
  • 예를 들어, A = 12인 경우 A를 이진수로 표현하면 1100이다.
  • -A의 이진수 표현 : '~A + 1' (비트 NOT 연산 후 1을 더해준다.)
    • ~A : 0011 (비트 반전)
    • ~A + 1 : 0100 (반전된 값에 1을 더함)
  • A & -A : 1100 & 0100 = 0100
  • 이때, 가장 오른쪽에 있는 1 비트를 찾아 반환한다.
  • 출력 : 4

 

◽ 최소 원소 지우기

A &= (A - 1)

• 집합에 포함된 가장 작은 원소를 지우는 방법이다.
  • 예를 들어, A = 12인 경우 A를 이진수로 표현하면 1100이다.
  • A - 1 : 1011
  • A &= (A - 1) : 1000

 

 

 

 

 

📃 reference

• https://gyoogle.dev/blog/algorithm/BitMask.html
• https://myeongju00.tistory.com/30