Number of 1 Bits
음이 아닌 정수 n이 주어집니다. n을 이진수로 표현하고 숫자 1의 개수를 반환하세요. 이 개수는 설정된 비트 수, 팝카운트 또는 해밍 가중치라고도 합니다. 예를 들어, 6은 이진수로 110이므로 1 비트가 두 개 있습니다.
함수
- ninteger
- 부호 있는 32비트 정수에 들어가는 음이 아닌 정수
- 반환값integer
- n의 이진수 표현에서 1의 자릿수
제약 조건
0 ≤ n ≤ 231-1
예제
- 입력
- n = 11
- 출력
- 3
- 설명
- 11은 2진수로
1011이며, 이는 8 + 2 + 1입니다. 네 개의 2진 숫자 중 세 개가 1이므로 답은 3입니다.
- 입력
- n = 128
- 출력
- 1
- 설명
- 128은 2^7이며,
10000000으로 씁니다. 1 하나 뒤에 0들이 이어지므로 답은 1입니다.
- 입력
- n = 2147483645
- 출력
- 30
- 설명
- 2^31-1 = 2147483647은 1비트가 31개 연속으로 있는 수입니다. 2147483645는 그 수에서 2를 뺀 값으로, 값이 2인 비트를 끄고 1이 30개 남습니다.
후속 질문
이 함수가 수백만 번 실행된다면, 미리 계산해 둔 개수가 담긴 256개 항목의 테이블을 네 번 조회하여 32비트 숫자의 비트 수를 어떻게 셀 수 있을까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
n의 마지막 이진수 자릿수만 살펴보세요.n을 문자열로 바꾸지 않고 그 자릿수를 어떻게 읽을 수 있을까요? 그런 다음 다음 자릿수를 어떻게 마지막 자리로 가져올 수 있을까요?n & 1(또는n % 2)은 마지막 비트이며, 오른쪽으로 한 비트 시프트(또는 2로 나눈 뒤 내림)를 하면 마지막 비트가 제거됩니다.n이 0이 될 때까지 마지막 비트들을 더하세요.더 짧은 루프를 사용하려면
n & (n-1)을 사용하세요. 이것은 가장 낮은 1비트를 끈n입니다.n이 0에 도달하기 전에 이를 몇 번 적용할 수 있는지 세세요. 그러면 이진 자릿수마다 한 번이 아니라 1비트마다 한 번씩 루프가 실행됩니다.
풀이
문자열을 만들지 않고 n의 이진 자릿수를 확인합니다. 마지막 비트를 읽고 오른쪽으로 이동해 제거하면 이진 자릿수마다 한 단계씩, 최대 31단계가 걸립니다. n & (n-1)로 가장 낮은 1 비트를 지우면 1 비트마다 한 단계씩 걸리며, 이는 답과 정확히 같습니다.
마지막 부분을 확인하고 오른쪽으로 이동
핵심 아이디어
n & 1은 n의 마지막 이진 숫자입니다. n이 홀수이면 1, 짝수이면 0입니다. 이를 개수에 더합니다. 그런 다음 n >> 1은 해당 숫자를 제거하고 다음 숫자를 마지막 자리로 옮깁니다. 음수가 아닌 수에서는 2로 나눈 몫을 내림한 것과 같습니다. 11, 즉 1011의 경우, n이 0으로 줄어들면서 마지막 비트는 1, 1, 0, 1 순으로 읽힙니다. 즉 1 비트는 세 개입니다.
반복문은 n이 0일 때 멈추므로 선행 0은 방문하지 않습니다. 단계 수는 대략 log2(n)이며, 128에서는 8회이고 최대 31회입니다. n과 개수만 저장합니다.
알고리즘
- 카운터를 0에서 시작합니다.
n이 0보다 큰 동안n & 1을 카운터에 더합니다.n을 오른쪽으로 1비트 시프트합니다.n이 0이 되면 카운터를 반환합니다.
def hammingWeight(n):
count = 0
while n > 0:
count += n & 1 # the last bit is 1 or 0
n >>= 1 # drop the last bit
return countn & (n-1)로 가장 낮은 위치의 설정 비트를 지웁니다
핵심 아이디어
1을 빼면 가장 낮은 위치의 1비트가 0으로 바뀌고 그 아래의 모든 0은 1로 바뀌며, 그 위의 비트는 그대로 유지됩니다. 따라서 n & (n-1)은 상위 비트를 유지하고 가장 낮은 위치의 1비트를 지웁니다. 12는 1100이고, 11은 1011이며, 1100 & 1011은 1000입니다.
각 단계에서 1비트가 정확히 하나씩 제거되므로, n이 0이 될 때까지 필요한 단계 수가 정답입니다. 128은 8단계 대신 1단계가 걸리지만, 2^31-1은 여전히 31단계가 걸립니다. Lua 5.1에는 비트 연산자가 없으므로, Lua 5.1 버전은 절반씩 나누고 그 값을 빼서 가장 낮은 위치의 1비트를 찾습니다. 루프는 여전히 1비트마다 한 번씩 실행됩니다.
알고리즘
- 카운터를 0으로 시작합니다.
n이 0이 아닌 동안n을n & (n-1)로 바꿉니다.- 바꿀 때마다 카운터에 1을 더합니다.
- 카운터를 반환합니다.
def hammingWeight(n):
count = 0
while n != 0:
n &= n - 1 # turn off the lowest 1 bit
count += 1
return count
함정과 경계 사례
n > 1인 동안 반복합니다. 반복문은 마지막 1비트 전에 멈추며n = 1일 때 0을 반환합니다.- 실수로 나눕니다. JavaScript, Lua, R에서는
11 / 2가 5.5이며, 이어지는 나머지는 분수가 됩니다.Math.floor,math.floor또는%/%를 사용해 내림하거나, 대신 시프트하세요. - Lua 5.1에서
n & 1을 작성합니다. 비트 연산자가 없으므로 코드가 컴파일되지 않습니다.n % 2와math.floor(n / 2)를 사용하세요.
자주 묻는 질문3
Number of 1 Bits의 시간 복잡도는 얼마인가요?
시프트 루프는 각 이진 숫자마다 한 번 실행됩니다. 즉, 여기서는 최대 31단계인 O(log n)입니다. n & (n-1) 루프는 1비트마다 한 번 실행됩니다. 즉, 답인 k에 비례하는 O(k)입니다. 두 루프 모두 추가 공간은 O(1)을 사용합니다.
설정된 비트 수를 세는 내장 함수가 있나요?
대부분의 언어에는 이 기능이 있으며, 단일 프로세서 명령어를 기반으로 구현된 경우가 많습니다. Java의 Integer.bitCount, GCC의 __builtin_popcount, Go의 bits.OnesCount, Rust의 count_ones, 그리고 Python 3.10 이상 버전의 int.bit_count가 있습니다. 면접에서는 반복문을 작성하고 내장 기능에 대해서도 언급하세요.
해밍 가중치와 해밍 거리의 차이는 무엇인가요?
숫자의 해밍 가중치는 이진 자릿수 중 1인 자릿수의 개수이며, 이 문제는 그 값을 반환합니다. 두 숫자 사이의 해밍 거리는 비트 위치가 서로 다른 개수입니다. 두 숫자가 다른 위치만 정확히 설정하는 XOR 연산의 결과인 a ^ b에서 1 비트의 개수를 세면 됩니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def hammingWeight(n):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자
n = 11
예상 출력
3