비트 연산으로 순열 동작하는 코드를 'in' 연산이랑 비교하고자 한다.

in

import time
current = time.time()

n, r = map(int, input().split())
arr = []

def permutation(arr):
    if len(arr) >= r:
        # print(*arr, sep=' ')
        return
    
    for i in range(1, n+1):
        if i not in arr:
            arr.append(i)
            permutation(arr)
            arr.pop()

permutation(arr)
print(time.time() - current)

# 20, 5 기준으로
# 1.26초

bitwise, 미완성 코드

import time
current = time.time()

n, r = map(int, input().split())

def permutation(bit_num):
    if bit_num.bit_count() >= r:
        arr = []
        cnt = 0
        while True:
            if not bit_num:
                return
            
            num = bit_num % 2
            # print(num if num else 0, sep=' ')
            bit_num //= 2
    
    for i in range(n):
        tmp = 1 << i
        if not bit_num & tmp:
            bit_num, tmp = bit_num | tmp, bit_num
            permutation(bit_num)
            bit_num = tmp
            

permutation(0)
print(time.time() - current)

# 상당히 느린 것을 확인

결론

• 우선 bitwise는 순서를 기억할 수 없다. 따라서 조합은 가능하다.
• bitwise가 더 좋을 줄 알았지만 bit를 다시 수로 복구하는 과정에서 기존보다 더 많은 연산을 필요로 한다. 따라서 몇 배는 느린 속도를 보여준다.
• 비트 연산으로 빠르게 처리한 다른 문제를 보고 영감을 얻어 시도해 봤는데 적용할 수 있는 상황이 한정적임을 깨달았다.