파이썬으로 특정 비트 범위 내 설정되지 않은 비트 개수 세기

양수 하나와 비트 범위가 주어졌을 때, 해당 범위 안에 있는 설정되지 않은 비트(unset bit), 즉 값이 0인 비트의 개수를 구하는 문제입니다.

입력 : n = 50, 시작 위치 = 2, 끝 위치 = 5
출력 : 2

비트 위치 2부터 5 사이에는 '0'인 비트가 총 2개 존재합니다.

알고리즘

문제를 해결하는 절차는 다음과 같습니다.

1단계 : bin() 함수를 사용해 n을 이진수 문자열로 변환한다.
2단계 : 앞의 두 문자('0b')를 제거한다.
3단계 : 문자열을 뒤집는다.
4단계 : 인덱스 l-1부터 r까지(r은 미포함) 범위에서 '0'인 비트의 개수를 센다.

문자열을 뒤집는 이유는 이진수의 가장 오른쪽 비트가 최하위 비트(LSB), 즉 0번째 위치에 해당하기 때문입니다. 뒤집으면 왼쪽에서 오른쪽으로 읽으며 각 비트의 실제 위치와 일치시킬 수 있습니다.

예제 코드

# 주어진 범위 내 설정되지 않은 비트 개수를 세는 함수

def countunsetbits(n, st, ed):
    # n을 이진수로 변환
    bi = bin(n)
    # 앞의 두 문자('0b') 제거
    bi = bi[2:]
    # 문자열 뒤집기
    bi = bi[-1::-1]
    # 인덱스 st-1부터 ed까지(ed는 미포함) '0'인 비트 개수 세기
    print(len([bi[i] for i in range(st-1, ed) if bi[i] == '0']))

# 드라이버 프로그램
if __name__ == "__main__":
    n = int(input("양수를 입력하세요 ::>"))
    st = int(input("시작 위치를 입력하세요"))
    ed = int(input("끝 위치를 입력하세요"))
    countunsetbits(n, st, ed)

실행 결과

양수를 입력하세요 ::> 50
시작 위치를 입력하세요2
끝 위치를 입력하세요5
2

숫자 50의 이진 표현은 110010이며, 이를 뒤집으면 010011이 됩니다. 시작 위치 2부터 끝 위치 5 직전까지 확인하면 인덱스 2와 3의 비트가 '0'이므로 결과는 2가 됩니다.