양의 정수를 이진수로 변환하면 값이 1인 비트들이 존재합니다. 이처럼 1로 표시되는 비트를 설정 비트(set bit)라고 부릅니다. 이 글에서는 주어진 숫자를 이진수로 변환한 뒤, 지정된 범위 안에 있는 설정 비트의 개수를 구하는 두 가지 방법을 살펴보겠습니다.
방법 1: bin 함수와 슬라이싱 활용
아래 예제에서는 먼저 bin() 함수를 사용해 숫자의 이진수 값을 얻습니다. 그다음 슬라이싱으로 이진수 변환 시 자동으로 붙는 0b 접두사를 제거하고, 문자열을 뒤집어 가장 오른쪽 비트부터 인덱스를 매깁니다. 마지막으로 range 함수를 이용해 l번째부터 r번째까지의 범위에서 값이 '1'인 비트만 골라 개수를 세면 됩니다.
예제 코드
def SetBits_cnt(n, l, r):
bin_val = bin(n)
# 이진수 변환 시 붙는 '0b' 접두사 제거
bin_val = bin_val[2:]
print(bin_val)
# 문자열 뒤집기 (오른쪽 끝이 인덱스 0이 되도록)
bin_val = bin_val[-1::-1]
# 인덱스 l-1부터 r-1까지 값이 '1'인 비트 개수 세기
print(len([bin_val[i] for i in range(l - 1, r) if bin_val[i] == '1']))
SetBits_cnt(83, 1, 6)
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
1010011
3
숫자 83을 이진수로 변환하면 1010011이 되며, 오른쪽에서 1번째부터 6번째까지의 비트 중 값이 1인 것은 총 3개입니다.
방법 2: 비트 연산자 활용
비트 연산자를 사용하면 더 효율적으로 설정 비트를 셀 수 있습니다. 아래 예제에서는 먼저 시프트 연산과 XOR 연산을 조합해 l번째 비트부터 r번째 비트까지만 1로 설정된 마스크(mask)를 만듭니다. 그런 다음 원래 숫자와 마스크를 AND 연산하여 해당 범위의 비트만 남긴 후, 별도의 함수로 설정 비트의 개수를 계산합니다.
예제 코드
def trackBitsInRange(n, l, r):
# 비트 연산자로 범위 마스크 생성
bit_num = ((1 << r) - 1) ^ ((1 << (l - 1)) - 1)
# 비트 연산 결과에서 설정 비트 개수 계산
return trackSetBits(n & bit_num)
def trackSetBits(n):
count = 0
while (n):
n &= (n - 1)
count = count + 1
return count
print(trackBitsInRange(83, 1, 6))
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
3
여기서 n &= (n - 1) 연산은 숫자에서 가장 오른쪽에 있는 1비트를 하나씩 제거하는 잘 알려진 기법입니다. 이 과정을 반복하면서 연산 횟수를 세면 전체 숫자를 한 비트씩 검사하는 것보다 빠르게 설정 비트의 개수를 구할 수 있습니다.
마무리
두 방법 모두 동일하게 3이라는 결과를 반환하지만, 문자열 변환 없이 비트 연산만으로 처리하는 두 번째 방법이 성능 면에서 더 유리합니다. 숫자의 크기가 크거나 반복 호출이 많은 상황이라면 비트 연산자 기반 접근 방식을 사용하는 것이 좋습니다.