: 집합을 메모리&시간 효율적으로 다루는 방법
🙋🏻♀️ 비트마스킹 장점
다른 자료 구조에 비해 수행 시간이 더 빠르다.
⇒ 대부분의 연산이 O(1)의 시간복잡도를 가진다.
Ex) 특정 원소의 존재여부를 판단할 때 선형탐색할 필요 없이 AND 연산 결과가 0이 아닌지 체크해서 검사한다.
비트 연산자를 사용하여 코드가 더 간결해진다.
⇒ 집합을 배열의 인덱스로 표현할 수 있다.
비트마스크를 사용하여 더 작은 메모리를 사용할 수 있다.
⇒ boolean type 으로 배열의 방문 체크를 하는 경우에는 1byte를 사용하지만 비트마스킹을 사용하면 1bit로 방문 체크를 함으로써 메모리를 줄일 수 있다.
DP나 순열 등 배열 활용만으로 해결할 수 없는 문제
000011 & 001001 = 000001
000011 | 001001 = 001011
000011 ^ 001001 = 001010
~000011 = 111100
000011 << 001001 = 000000
14 >> 3 = 00001110(14) >> 3 = 00000001(1)
🙋🏻♀️ 주의!
boolean a = (6&3 == 2);
// a = 0 (비교연산자 "==" 가 먼저 수행된다.)
[Java] 비트(bit)와 비트마스크(bit mask)
int A = 0; // 0(공집합)
A = (A<<10) - 1 // 1023
int A = A | (1<<k); // k번째 비트의 값을 1로 변경한다.
n | (1<<i) → 두 비트 중 한 비트라도 1이 나오면 1이 나온다.
Ex) 23 | (1<<3) int A = A & ~(1<<k); // k번째 비트의 값을 0으로 변경한다. (삭제)
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)
//XOR 연산
int A = A ^ (1<<k); // A집합에 해당 원소가 빠져있는 경우에는 추가하고, 들어있는 경우에는 삭제하는 방법이다.
A | B // A와 B의 합집합
A & B // A와 B의 교집합
A & (~B) // A에서 B를 뺀 차집합
A ^ B // A와 B중 하나만 포함된 원소들의 집합
Integer.bitCount(A); // 집합에 포함된 원소의 크기를 구하는 경우네는 A에서 켜진 bit의 수를 구하는 것이다.
int first = A & (-A); // 집합에 포함된 가장 작은 원소(index가 가장 작은 원소)를 찾는 방법이다. 켜져 있는 bit 중에서 가장 오른쪽에 있는 bit를 찾는 것이다.
int A = A & (A-1); // 가장 오른쪽에 켜져 있는 bit를 지우고 싶은 경우에는 A-1 과 AND연산을 시키면 된다.
// A에서 1을 빼주게 되면 가장 오른쪽에 있던 bit는 0이 되고 그보다 오른쪽에 있는 bit들이 1이 되기 때문이다.