파이썬의 비트마스크

컴퓨터는 내부적으로 이진수(비트)를 사용합니다. 그렇기 때문에 십진수 혹은 불린형을 사용하는 것보다 이진수를 사용하여 데이터를 표현하는 것이 더 효과적인 경우가 있습니다. 이렇게 이진수로 데이터를 표현하는 방식을 비트마스크라고 합니다.

파이썬이 지원하는 비트 연산자는 다음과 같습니다.

1. & : AND 연산
2. | : OR 연산
3. ^ : NOR 연산
4. ~ : NOT 연산
5. <<, >> : 쉬프트 연산

파이썬이 지원하는 연산자들을 이용하여 비트마스크를 다양하게 조작해보겠습니다. 들어가기 앞서 파이썬에서 제공하는 bin함수는 '수를 이진수 문자열로 바꾸어 출력에 용이하게 해줄 뿐' 실제 형변환이 되거나 그러진 않습니다. 따라서 일반적인 정수로 연산 및 변수 할당을 진행하면 됩니다. 우선 비트마스크는 0으로 초기화하겠습니다.

bitmask = 0
print('원본')
print(bin(bitmask))

파이썬은 보기 좋게 '0b0'이라고 출력합니다. 0b는 이진수를 표시하며, 뒤의 숫자가 실제 값입니다. 

 

원소 추가

loc = 2
print('원소 추가')
bitmask |= (1 << loc)
print(bin(bitmask))

1 << loc은 loc값만큼 1을 왼쪽으로 옮기며, 남은 오른쪽 자리는 0으로 채웁니다. 이를 원본 비트마스크와 OR 연산하면 원하는 위치만 1로 바꿀 수 있습니다.

 

원소 삭제

print('원소 빼기')
bitmask &= ~(1 << loc)
print(bin(bitmask))

위에서 추가했던 원소를 삭제하려면 방금 위치를 나타냈던 쉬프트 연산값에 NOT을 취한 뒤 비트마스크와 AND 연산합니다. 이러면 우항이 필터같은 역할을 하여 삭제할 위치 이외의 원소만 통과시키게 됩니다.

 

원소 토글

print('원소 빼기')
bitmask &= ~(1 << loc)
print(bin(bitmask))

XOR 연산자를 사용하면 켜져있는 원소는 끄고, 꺼진 원소는 켤 수 있습니다.

 

집합 크기

print('집합 크기')
def bit_count(x):
    if (x == 0): return 0
    return x % 2 + (bit_count(x // 2))
print(bit_count(bitmask))

켜져 있는 비트의 개수를 세고 싶을 때, 즉 1의 개수를 세고 싶을 때 위와 같이 재귀적으로 호출할 수 있습니다. 0의 개수만큼 2로 나누어떨어지며, 1의 개수만큼 1을 더하게 됩니다. 1 // 2 = 0으로 최종적으로 0이 나오면 종료합니다.

 

최소 원소

print('최소 원소')
print(bin(bitmask & -bitmask))

최소 원소는 비트마스크와 비트마스크의 2의 보수를 AND 연산하면 얻을 수 있습니다. 2의 보수는 비트마스크에 NOT 연산한 뒤 1을 더하게 되는데, 결과적으로 최하위비트부터 가장 작은 원소까지 모두 1이 되어 AND 연산을 통해 가장 빨리 발견되는 값이 최소값이 됩니다.

 

최소 원소 삭제 

print('최소 원소 삭제')
bitmask &= bitmask - 1
print(bin(toppings))

최소 원소를 삭제할 때는 조회 후 삭제보다 빠른 방법이 있습니다. 비트마스크에서 1을 뺀 결과와 AND 연산합니다. 좌항의 경우 최소 원소 직전까지 모두 1로 변하고, 최소 원소의 자리는 0이 됩니다. 따라서 AND 연산할 경우 최소 원소만 꺼지게 됩니다.

 

부분집합 순회

print('부분집합 순회')
bitmask |= (1 << 5)
bitmask |= (1 << 7)
subset = bitmask
idx = 1
while subset:
    print(idx, bin(subset))
    subset = ((subset - 1) & bitmask)
    idx += 1

비슷한 원리로 부분집합을 순회하는 것도 가능합니다. (subset - 1) & bitmask라는 표현은 결국 원소를 하나씩 지워가면서 모두 출력하겠다라는 의미로 파악할 수 있습니다.