[DevLog] 2진수 표현에서 1의 개수 세기

2진수 표현에서 1의 개수는 일반적으로 2로 나누어주고, 그 나머지를 카운팅하며 셀 수 있다. 시간복잡도 $O(logN)$

def func(N):
    cnt = 0
    while N:
        cnt += N % 2
        N //= 2

    return cnt

bitwise 연산자를 사용하면 이와 유사한 방법으로 1의 개수를 셀 수 있다. 주어진 수 N의 가장 오른쪽 비트가 1인지 확인하고, N을 하나씩 right shift하면서 1의 개수를 센다. 이는 N의 비트수만큼 시간이 걸린다. 시간복잡도 $O(logN)$

def func(N):
    cnt = 0

    while N:
        cnt += N & 1  # 현재 가장 오른쪽 비트가 1인지 확인
        N >>= 1       # N을 오른쪽으로 1 비트씩 이동하여 다음 비트 확인

    return cnt

이보다 더 나은 방법은 Brian Kernighan의 알고리즘이라고 불리는 방식이다. N = N & (N-1) 을 반복하면서 가장 오른쪽 비트를 제거한다. 그리고 그 횟수를 센다. N을 이진수로 나타내었을 때 1의 개수만큼 반복하므로, 이진 표현에서 1이 적은 경우 위 두 경우보다 더 빠르다. 시간복잡도 $O(k)$ (k는 1의 개수)

def func(N):
    cnt = 0
    while N:
        N = N & (N-1)
        cnt += 1
    return cnt

시도해 본 방법 중 가장 빠른 것은 파이썬의 bin 내장함수를 활용하는 것이다. 내부적인 최적화로 인해 실행 시간이 나머지 세 방법보다 가장 빨랐다.

def func(N):
    binary = bin(N)[2:]  # 2진수로 변환 후 'Ob' 제거
    cnt = binary.count('1')
    return cnt

백준 2098: 외판원 순회 를 풀다가 접한 비트마스킹 개념을 공부하면서, 늘 헷갈렸던 비트 연산에 대해 조금 더 공부해볼 수 있는 기회 (코치님의 피드백)가 생겨 얕게나마 파보았다.. 비트마스킹을 이용해 방문한 도시 (0..N)를 나타낼 경우 최대 63개의 도시까지 방문을 체크할 수 있는데 이는 파이썬에서 정수형이 8바이트기 때문이다. 8바이트는 64비트지만 양수/음수를 나타내는 사인 비트가 1비트를 차지하므로 최대 63비트까지만 사용할 수 있게 된다.

비트연산자 | & << >> 에 더욱 익숙해지고 싶다.. 비트 연산을 잘 이해하면 이해할수록, 컴퓨터의 동작 방식에 대해서도 잘 이해하게 될 것 같다는 생각이 들었다. (하나가 다른 하나의 원인이 된다는 것이 아니고 이해도가 깊어지는 방향이 같다는 의미에서)

random_numbers = []
for _ in range(100):
    num = random.randint(2**62, 2**63 - 1)
    random_numbers.append(num)

위 인풋에서 순서대로 아래와 같은 결과를 뱉는다. 1은 내장함수, 2는 커니핸, 3은 나누기 반복, 4는 비트 시프트. 의문점은: 3과 4가 매번 근사하지만 늘 3이 4보다 빠른 실행시간을 보였는데, 비트 시프트보다 나누기가 왜 더 성능이 좋은지가 궁금하다. 답을 찾게 되면 덧붙여 두어야겠다.

func 1: 32, 0.00006 sec
func 2: 32, 0.00020 sec
func 3: 32, 0.00041 sec
func 4: 32, 0.00043 sec