비트마스킹

Jinjin·2023년 3월 23일
1

1. 비트마스킹이란?

: 집합을 메모리&시간 효율적으로 다루는 방법

🙋🏻‍♀️ 비트마스킹 장점

  1. 다른 자료 구조에 비해 수행 시간이 더 빠르다.

    ⇒ 대부분의 연산이 O(1)의 시간복잡도를 가진다.

    Ex) 특정 원소의 존재여부를 판단할 때 선형탐색할 필요 없이 AND 연산 결과가 0이 아닌지 체크해서 검사한다.

  2. 비트 연산자를 사용하여 코드가 더 간결해진다.

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

  3. 비트마스크를 사용하여 더 작은 메모리를 사용할 수 있다.

    ⇒ boolean type 으로 배열의 방문 체크를 하는 경우에는 1byte를 사용하지만 비트마스킹을 사용하면 1bit로 방문 체크를 함으로써 메모리를 줄일 수 있다.

  4. DP나 순열 등 배열 활용만으로 해결할 수 없는 문제

2. 비트 연산

  • AND 연산 : A&B (두 비트 모두 1이면 1)
    000011 & 001001 = 000001
  • OR 연산 : A|B (두 비트 중 1개만 1이면 1)
    000011 | 001001 = 001011
  • XOR 연산 : A^B (두 비트가 서로 다르면 1)
    000011 ^ 001001 = 001010
  • NOR 연산 : ~A (비트 반전(보수))
    ~000011 = 111100
  • A << B ( 왼쪽으로 B만큼 이동한다 )
    000011 << 001001 = 000000
  • A >> B ( A의 각 비트를 y만큼 오른쪽으로 이동, 왼쪽 빈자리는 A의 최상위 부호비트와 같은 값으로 채워진다.)
    14 >> 3 = 00001110(14) >> 3 = 00000001(1)
  • A >>> B : A의 각 비트를 B만큼 오른쪽으로 이동, 왼쪽 빈자리는 0으로 채워진다.

🙋🏻‍♀️ 주의!

  • 연산자 우선순위 망각하기
    boolean a = (6&3 == 2);
    // a = 0 (비교연산자 "==" 가 먼저 수행된다.)

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

[Java] 비트(bit)와 비트마스크(bit mask)

3-1. 공집합과 꽉 찬 집합 구하기

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

3-2. 원소 추가

int A = A | (1<<k); // k번째 비트의 값을 1로 변경한다.
  • i번째 비트의 값을 1로 변경하려면?
    n | (1<<i) → 두 비트 중 한 비트라도 1이 나오면 1이 나온다.
    Ex) 23 | (1<<3)

3-3. 원소 삭제

int A = A & ~(1<<k); // k번째 비트의 값을 0으로 변경한다. (삭제)

3-4. 원소의 포함 여부 확인

if((A & (1<<k)) != 0); // k번째 원소가 포함되어 있는지 확인할 수 있다.
  • 이진수 001001에서 i번째 비트가 1인지 혹은 0인지 확인하는 방법은?

    확인할 숫자를 n이라고 하고 i번째 비트를 확인하고 싶다?

    n & (1<<i)
    
    if(n & (1<<i)0이다?) → i번째 비트는 0이다.
    if(n & (1<<i)0이 아니다?) → i번째 비트는 1이다.

    Ex1) 23 & (1<<2)

    Ex2) 23 & (1<<3)

3-5. 원소의 토글


//XOR 연산
int A = A ^ (1<<k); // A집합에 해당 원소가 빠져있는 경우에는 추가하고, 들어있는 경우에는 삭제하는 방법이다.

3-6. 두 집합에 대해 연산하기

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

3-7. 집합의 크기 구하기

Integer.bitCount(A); // 집합에 포함된 원소의 크기를 구하는 경우네는 A에서 켜진 bit의 수를 구하는 것이다.

3-8. 최소 원소 찾기

int first = A & (-A); // 집합에 포함된 가장 작은 원소(index가 가장 작은 원소)를 찾는 방법이다. 켜져 있는 bit 중에서 가장 오른쪽에 있는 bit를 찾는 것이다.

3-9. 최소 원소 지우기

int A = A & (A-1); // 가장 오른쪽에 켜져 있는 bit를 지우고 싶은 경우에는 A-1 과 AND연산을 시키면 된다.
// A에서 1을 빼주게 되면 가장 오른쪽에 있던 bit는 0이 되고 그보다 오른쪽에 있는 bit들이 1이 되기 때문이다.
profile
BE Developer

0개의 댓글