집합의 요소들의 구성 여부를 표현할 때 유용한 테크닉
9(10진수) -> 1001(2진수)
0과 1로, flag 활용하기
[1,2,3,4,5]라는 집합이 있다.
여기서 임의로 몇 개를 골라 뽑아서 확인을 해야하는 상황이 주어졌다. (즉, 부분집합을 의미)
{1}, {2} , ... , {1,2} , ... , {1,2,5} , ... , {1,2,3,4,5}
물론, 간단히 for문을 돌려가며 배열에 저장하며 경우의 수를 구할 순 있다.
하지만, 비트마스킹을 하면, 각 요소를 인덱스처럼 표현하여 효율적인 접근이 가능하다.
[1,2,3,4,5] → 11111
[2,3,4,5] → 11110
[1,2,5] → 10011
[2] → 00010
집합의 i번째 요소가 존재하면 1, 그렇지 않으면 0을 의미한다.
이러한 2진수는 다시 10 진수로 변환도 가능하다.
11111
은 10진수로 31이므로, 부분집합을 정수를 통해 나타내는 것이 가능하다는 것을 알 수 있다.
이로써, 해당 부분집합에 i를 추가하고 싶을 때 i번째 비트를 1로만 바꿔주면 표현이 가능해졌다.
이런 행위는 비트 연산을 통해 제어가 가능하다.
AND, OR, XOR, NOT, SHIFT
[왼 쪽] 0001 → 0010 → 0100 → 1000 : 1 → 2 → 4 → 8
[오른쪽] 1000 → 0100 → 0010 → 0001 : 8 → 4 → 2 → 1