비트마스크(BitMask) 파이썬에서 활용하기

비트마스크 기법은 비트를 "참 거짓 여부를 담고있는 리스트"처럼 활용하는 것이다.

마치 DFS나 BFS의 visited리스트처럼 True/False가 담긴 리스트를 활용해 본 적이 있을것이다.

동일한 기능을 더 적은 메모리와 더 빠른 속도로 수행할 수 있도록 하는 테크닉이 비트마스크이다.

 

AND(&), OR(|), XOR(^), NOT(not), SHIFT(>> , <<)를 활용한다.

 

2진수로 출력하려면 다음과 같은 함수를 활용한다

def print2th(num):
    result=""
    while num > 0:
        result += str(num%2)
        num = num//2
    print(result[::-1])

 

i번째 비트를 True로 바꾸고 싶다면 다음과 같은 방법을 사용한다.

visited |= 1<<(i)

index가 0부터 시작한다고 가정하였다.

1부터 시작한다고 생각해야 할 경우 i 대신 i-1을 넣어주면 된다.

 

i번째 비트를 False로 바꾸고 싶다면 다음과 같은 방법을 사용한다.

visited &= not(1<<i)

 

i번째 비트가 True인지 검사하려면 다음과 같은 방법을 사용한다

if (visited&(1<<i)):
	#....

False인지를 검사하려면 그냥 위에 not을 붙여주면 된다.