[알고리즘] 비트마스킹 - 파이썬

비트마스킹을 활용하여 원소의 개수 n이 주어질 때

모든 조합의 경우의 수를 구할 수 있다. 

n = 4
for i in range(1<<n):
    nums = []
    for j in range(n):
        if i&(1<<j):
            nums.append(j)
    print(*nums)

결과는 다음과 같다.

0
1
0 1
2
0 2
1 2
0 1 2
3
0 3
1 3
0 1 3
2 3
0 2 3
1 2 3
0 1 2 3

무슨 원리일까?

 

1. << 연산

for i in range(1<<n):

우선 처음 반복문에 나오는 이것. << 연산은 비트 연산으로, 비트를 왼쪽으로 한칸씩 밀어내는 연산자이다.

1은 2진법으로 00001로 표현되는데

만약 1<<1이면 비트를 한칸씩 밀어내서 00010이 되고(십진법으론 2)

1<<2이면 같은 방식으로 00100이 되고(십진법으론 4)

여기서 n이 4이므로 10000이 된다.(십진법으론 16)

 

근데 이때 1<<4는 16인데 16은 원소 4개로 만들수있는 조합의 경우의 수와 같다. 

여기서 비트마스킹을 사용하는 이유가 드러난다. 

비트를 통해 존재하는 원소를 1, 존재하지 않는 원소를 0 으로 대응시키면

1<<n 가지의 케이스에 모든 경우의 수를 대응시킬 수 있다. 

 

다시 말하면 0000~1111에 각 숫자 0~15을 대응시킬 수 있다.

 

 

2. 비트 연산 스킬

if i&(1<<j):

여기서 i&(1<<j)가 의미하는 바는 

i라는 숫자의 비트에서, 오른쪽으로부터 j번째 자리가 1인가? 라는 뜻이다.

 

예를 들어 i = 7이라고 해보자. 비트로는 0111가 될 것이다.

j는 2라고 해보자. 1<<j는 그럼 1<<2이므로 0100이 된다. 

이제 비트 연산 중 &연산을 해보자. &는 And 연산으로, 둘 다 1이면 1, 나머지 경우는 0으로 계산하는 연산이다.

0111&0100을 그럼 해보면 0100이된다. 

잘 생각해보면 (1<<j)는 어차피 1이 j번째에만 존재한다. 이 자리에 1이 있으면 i&(1<<j)결과는 무조건 1이 나올테고 

이 자리가 0이면 i&(1<<j) 결과는 무조건 0이 나온다. 즉 이 자리에 1이 있냐 없냐하는 결과를 리턴하는 것이다.