[알고리즘] 비트마스크 Bit Mask

비트마스크 

• 꺼져있다 = 0, 켜져있다 = 1 로 표현할 수 있는 2진수의 특성을 활용해 자료구조로 활용하는 기법.
• 비트를 마스킹처리하여 비트 연산을 활용해 2진 비트를 처리하는 작업이다.

장점

1. 수행 시간이 빠르다.

• 다른 자료구조에 비해 수행 시간이 빠르다. 비트 마스크 연산은 비트Bit 연산으로 O(1)로 동작한다.

2. 간결한 코드

• 다양한 집합 연산들을 비트연산자 한 줄로 작성할 수 있기 때문에 코드가 간결해진다.

3. 적은 메모리 사용량

• 2진수의 특성상 하나의 정수로 많은 경우의 수를 표현할 수 있기 때문에 메모리를 효율적으로 활용할 수 있다.

비트연산자

[JavaScript] 비트 연산 Bit Operation

---

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

• 비트마스크를 이용하면 집합의 연산을 빠르게 수행할 수 있다. 
• 원소의 갯수가 N개인 집합이 있다고 할 때, 각 원소를 0번부터 (N-1)번까지 번호를 부여하고, 하나씩 대응시켜 1이면 포함, 0이면 불포함하여 집합을 표현할 수 있다. 
• {A, B, C, D, E, F, G} 라는 집합이 있을 때, 전체 집합은 1111111(2) 와 같이 표현할 수 있다.

연산	사용 예시
공집합과 꽉 찬 집합 구하기	A = 0; / A = (1 << 10) - 1;
원소 삭제	A &= ~(1 << k);
원소 추가	A |= (1 << k);
원소의 포함 여부 확인	if(A & (1 << k))
원소의 토글(toggle)	A ^= (1 << k);
두 집합에 대해서 연산	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); } [내장 명령어] gcc/g++ → __builtin_popcount(A)  visual C++ → __popcnt(A) Java → Integer.bitCount(A)
최소 원소 찾기	int first = A & (-A);
최소 원소 지우기	A &= (A - 1);
모든 부분 집합 순회하기	for (int subset = A ; subset ; subset = ((subset - 1) & A)){ }

출처 : https://rebro.kr/63 [Rebro의 코딩 일기장]

공집합과 꽉찬 집합 구하기

• 공집합 : 비트가 모두 꺼진 (0인) 상태이므로 A=0 은 공집합을 표현한다.
• 꽉 찬 집합 : 비트가 모두 켜진 (1인) 상태이므로 1111...1111(2)의 값을 가져야 한다. 

원소 삭제

k = 3;
A = (1<<10)-1; //1111111111(2)

A &= ~(1<<k); //1111110111(2)

• A &= ~(1<<k)
• A집합의 k번째 인덱스의 원소를 삭제한다. 해당 비트가 꺼져야 하기 때문에 항상 0으로 만드는 연산이 필요하다.
• (1<<k) = 1000(2), ~(1<<k) = 1111....0111(2)
• ~(1<<k) 마스크를 A와 AND 연산하면, 해당 인덱스의 비트는 0으로 초기화 되고, 나머지는 원래 값을 가진다.

원소 추가

k = 3;
A = (1<<10)-1; //1111111111(2)

A &= ~(1<<k); //1111110111(2)
A |= (1<<k);  //1111111111(2)

• A |= (1<<k)
• A집합의 k번째 인덱스에 특정 원소를 추가한다. 추가란 0에서 1로 켜는 것이므로 해당 비트를 1로 만들어야 한다.
• OR연산으로 둘 중 하나만 1이어도 1이 되도록 한다. 
• 이미 A원소에 포함되어 있는 경우에는 아무런 변화가 없다. (어차피 1이니까)

원소의 포함 여부 확인

k = 3;
A = (1<<10)-1; //1111111111(2)​

if(A&(1<<k)) //true

• k번째 원소가 켜져있는지 여부를 확인하면 된다. 

원소의 토글

k = 3;
A = (1<<10)-1; //1111111111(2)​

A ^= (1<<k); //1111110111(2)

• A집합에 해당하는 원소가 빠진 경우 추가, 있는 경우 삭제하는 방법이다.
• ^ XOR연산을 활용한다. 대응되는 비트가 서로 다를 경우 1을 반환하므로 결과적으로 반대의 값을 얻을 수 있다.

두 집합에 대한 연산

A = 9; //1001(2)
B = 5; //0101(2)

A | B //1101(2)    합집합
A & B //0001(2)    교집합
A & (~B) //1000(2) A-B 차집합
A ^ B // 1100(2)   A와 B중 하나에만 포함된 원소들의 집합

집합의 크기 구하기

• Stack Overflow에 자바스크립트로 비트 갯수를 구하는 아래와 같은 코드가 있어 참고하면 좋을 듯 하다. 
• 자바에는 Integer.bitCount(A) 와 같은 함수가 있다. (자바스크립트는 내장 함수는 따로 없는 것 같다.)

Number(i.toString(2).split("").sort().join("")).toString().length; //i는 32bit 이내

function bitCount (n) {
  n = n - ((n >> 1) & 0x55555555)
  n = (n & 0x33333333) + ((n >> 2) & 0x33333333)
  return ((n + (n >> 4) & 0xF0F0F0F) * 0x1010101) >> 24
}

console.log(bitCount(0xFF)) //=> 8

function bitCount (n) {
  return n.toString(2).match(/1/g).length
}

console.log(bitCount(0xFF)) //=> 8

출처 : https://stackoverflow.com/questions/43122082/efficiently-count-the-number-of-bits-in-an-integer-in-javascript

• 참고로 위 도표에 있는 자바 코드를 활용해 작성한 JS코드는 켜진 비트 갯수 * 2의 결과값을 도출했다.
• 이유를 잘 모르겠어서.. 아시는 분 계시면 댓글 부탁드립니다.

n=13; //1101(2)

function bitCnt(n){
    if(n===0) return 0;
    return n%2 + bitCnt(n/2)
}
//6

최소 원소 찾기

let first = A & (-A); //2

//     A =  1010(2)
//& (-A) = -0110(2)
-------------------
           0010(2)

• 집합에 포함된 가장 작은 원소 즉 켜져있는 비트 중 가장 오른쪽에 있는 것을 찾는 방법이다.
• (-A) = ~A+1 :  ~A의 가장 작은 자리에 1을 더하면 A의 2의 보수, 즉 음수가 된다. (2진수 상에서 2의 보수는 A와 더했을 때 0이 되는 수를 의미한다. 보수에 대한 내용은 여기를 참고했다.)
• -
• 가장 오른쪽에 켜져있는 비트를 k라고 했을 때, 0 ~ k-1의 비트는 모두 0이다. //1010
• ~A 에서 A가 반전되었으므로, k번째 비트는 0, 0 ~ k-1까지는 1이다. //0101
• ~A+1 에서 가장 작은 자리에 1을 더해주었으므로 k번째 비트는 1, 0 ~ k-1 까지의 비트는 모두 0이 된다. //0110
• 따라서 A와 -A를 AND 연산하면 k번째 비트만 켜진 상태로 남게 된다.

최소 원소 지우기

A &= (A-1);

//  1010(2)
//& 1001(2)
-------------
    1000(2)

• 집합의 가장 오른쪽, 최소 원소를 지우는 방법이다. 
• A - 1 은 가장 최소 비트를 0으로, 그보다 오른쪽 비트를 1로 만들기 때문에 A와 연산하면 최솟값을 0으로 초기화 할 수 있다.

모든 부분 집합 순회하기

for (let subset = A; subset>0; subset=((subset-1)&A)){
    console.log(subset.toString(2));
}

//A = 1101(2)

//1101(2)
//1100(2)
//1001(2)
//1000(2)
//0101(2)
//0100(2)
//0001(2)

• for문을 이용해 공집합을 제외한 부분집합을 모두 구할 수 있다. 그 과정은 아래와 같다.

subset	(subset - 1)	(subset - 1) & A
1101(2)	1100(2)	1100(2)
1100(2)	1011(2)	1001(2)
1001(2)	1000(2)	1000(2)
1000(2)	0111(2)	0101(2)
0101(2)	0100(2)	0100(2)
0100(2)	0011(2)	0001(2)
0001(2)	0000(2)	0000(2) 종료

---

정리

• 비트마스크는 2진수의 특성을 활용한 비트 연산으로, 정수를 자료구조로 활용할 수 있는 기법이다.
• 가장 대표적인 활용 예시는 집합의 표현과 집합 연산이 있고, 일반적인 완전탐색 알고리즘과 dp알고리즘에 응용할 수 있다.
• 자바스크립트 비트 연산자의 종류로는 & (교집합), | (합집합), ~, ^, <<, >>, >>>등이 있다.
• 값을 구할 수 있는 연산을 위한 원본의 마스크를 만들고, 원본과 마스크를 비교하는 연산을 통해 특정 값을 구할 수 있다.

참고자료

• https://rebro.kr/63#recentEntries
• https://travelbeeee.tistory.com/451
• https://velog.io/@jakeseo_me/2019-04-30-1604-%EC%9E%91%EC%84%B1%EB%90%A8-7qjv3gv9ad​

비트마스크 (BitMask) 알고리즘

[알고리즘] 비트마스킹(bitmasking) 이란

자바스크립트 개발자라면 알아야 할 33가지 개념 #12 자바스크립트 비트연산 실제로 활용하기!