비트 세기, 누락된 숫자와 비트 뒤집기
DP와 최하위 설정 비트 기법으로 0부터 n까지의 비트 개수를 계산하고, XOR로 누락된 숫자를 찾으며, 32비트 정수의 비트를 뒤집습니다.
비트 세기, 누락된 숫자와 비트 뒤집기은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 4번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
비트 세기 문제 개요
비트 세기 문제(LeetCode 338)는 n이 주어졌을 때, 크기가 n+1인 배열 ans를 반환하라고 합니다. 여기서 ans[i]는 i에 포함된 1비트의 개수입니다. 순진한 방법은 각 수의 비트를 개별적으로 세므로 O(n log n)입니다. DP 방법은 i와 i의 절반 또는 최하위 설정 비트 사이의 관계를 활용해 O(n)에 해결합니다.
DP를 가능하게 하는 핵심 관찰은 두 가지입니다. (1) i >> 1은 최하위 비트를 제거하므로 bits[i] = bits[i >> 1] + (i & 1)입니다. (2) 최하위 설정 비트를 제거하면 bits[i] = bits[i & (i-1)] + 1입니다. 두 방법 모두 O(n) 시간과 O(n) 공간(출력 배열에 필요한 공간)을 사용합니다.
def count_bits_v1(n):
# O(n log n): naive individual count
return [bin(i).count('1') for i in range(n + 1)]
def count_bits_dp(n):
# O(n): DP using right shift
dp = [0] * (n + 1)
for i in range(1, n + 1):
dp[i] = dp[i >> 1] + (i & 1) # i >> 1 drops last bit
return dp
def count_bits_dp2(n):
# O(n): DP using lowest-set-bit trick
dp = [0] * (n + 1)
for i in range(1, n + 1):
dp[i] = dp[i & (i - 1)] + 1 # i & (i-1) clears lowest set bit
return dp
n = 10
print('Naive:', count_bits_v1(n))
print('DP v1:', count_bits_dp(n))
print('DP v2:', count_bits_dp2(n))DP 점화식이 작동하는 이유
오른쪽 시프트 점화식 dp[i] = dp[i >> 1] + (i & 1)의 경우, 2로 나누기(오른쪽 시프트)는 the 마지막 비트를 제거합니다. 마지막 비트가 1이면 개수가 1 증가하고, 0이면 변하지 않습니다. 따라서 bits[i] = bits[i // 2] + (i mod 2)입니다.
최하위 설정 비트 점화식 dp[i] = dp[i & (i-1)] + 1의 경우, i & (i-1)은 가장 오른쪽의 1비트를 해제하므로 i보다 설정된 비트가 하나 적습니다. 따라서 개수는 the 감소한 값의 개수에 1을 더한 값입니다. 두 점화식 모두 i를 오름차순으로 처리하므로 더 작은 하위 문제를 항상 먼저 해결합니다.
# Trace both recurrences for i = 0..8
print('i | i>>1 | i&1 | dp[i>>1]+(i&1) | i&(i-1) | 1+dp[i&(i-1)]')
print('-' * 60)
dp = [0] * 9
for i in range(1, 9):
# Right shift method
v1 = dp[i >> 1] + (i & 1)
# Lowest set bit method
v2 = dp[i & (i - 1)] + 1
dp[i] = v1 # either works
print(f'{i:2d} ({bin(i)[2:]:4s}) | {i>>1:2d} | {i&1} | {v1} | {i&(i-1):2d} | {v2}')
print('\nFinal dp:', dp)누락된 수: XOR 및 합계 접근법
누락된 수 문제(LeetCode 268)는 [0, n] 범위에서 서로 다른 n개의 수가 들어 있는 배열과, 정확히 하나의 누락된 수를 주어집니다. XOR 접근법은 0부터 n까지의 모든 인덱스를 배열의 모든 값과 XOR합니다. 쌍을 이루는 값은 상쇄되고 누락된 수만 남습니다. 합계 접근법은 expected = n*(n+1)//2를 계산한 뒤 expected - sum(nums)을 반환합니다.
두 방법 모두 O(n) 시간과 O(1) 공간을 사용합니다. XOR 접근법은 고정 너비 정수를 사용하는 언어에서 잠재적인 오버플로를 피할 수 있어 더 안정적입니다. Python에서는 정수가 임의 정밀도를 지원하므로 두 방법 모두 문제없이 작동합니다.
def missing_xor(nums):
n = len(nums)
result = n
for i, val in enumerate(nums):
result ^= i ^ val # each index i cancels its matching value
return result
def missing_sum(nums):
n = len(nums)
return n * (n + 1) // 2 - sum(nums)
test_cases = [
[3, 0, 1], # missing 2
[0, 1], # missing 2
[9,6,4,2,3,5,7,0,1], # missing 8
[0], # missing 1
]
for nums in test_cases:
print(f'{nums} => XOR={missing_xor(nums)}, Sum={missing_sum(nums)}')32비트 정수의 비트 반전
비트 반전 문제(LeetCode 190)는 32비트 부호 없는 정수의 이진 표현을 반전하라고 합니다. 반복 방법은 입력의 32개 비트를 오른쪽에서 왼쪽으로 처리하고, 출력에서는 왼쪽에서 오른쪽으로 배치합니다. 각 반복에서는 n & 1로 가장 오른쪽 비트를 추출하고, 공간을 만들기 위해 the 출력을 왼쪽으로 시프트한 다음 비트를 OR하고 n을 오른쪽으로 시프트합니다.
32번 반복한 후 출력 정수에는 n의 32개 비트가 모두 반전된 순서로 들어 있습니다. 이는 O(32) = O(1)이며, 8비트 단위에 캐싱을 사용해 여러 번 호출하면 상각 O(1)입니다.
def reverse_bits(n):
result = 0
for _ in range(32):
result = (result << 1) | (n & 1) # shift result left, OR in rightmost bit
n >>= 1 # move to next bit
return result
# Test with known values
print(reverse_bits(0b00000010100101000001111010011100)) # 964176192
print(reverse_bits(0b11111111111111111111111111111101)) # 3221225471
print(reverse_bits(0)) # 0
print(reverse_bits(1)) # 2147483648 (bit 0 goes to bit 31)
print(reverse_bits(0b10000000000000000000000000000000)) # 1비트 반전: 분할 정복
더 빠른 O(log 32) = O(1) 방법은 분할 정복 교환을 사용해 비트를 반전합니다. 먼저 인접한 비트를 교환하고, 다음으로 인접한 2비트 그룹을 교환한 뒤, 4비트 그룹을 교환하는 식으로 진행합니다. 각 교환 단계에서는 마스크로 번갈아 나타나는 그룹을 분리하고 시프트하여 서로 끼워 넣습니다. 5번 교환하면 32개 비트가 모두 반전됩니다.
이 방법은 입력과 관계없이 O(1)의 고정된 연산만 사용하므로 하드웨어 구현에서 활용됩니다. 마스크는 상수입니다. 0x55555555(번갈아 나타나는 01 패턴), 0x33333333(번갈아 나타나는 0011), 0x0f0f0f0f(번갈아 나타나는 00001111) 등이 있습니다.
def reverse_bits_dc(n):
# Treat n as 32-bit unsigned
n &= 0xFFFFFFFF
# Swap adjacent bits
n = ((n & 0x55555555) << 1) | ((n >> 1) & 0x55555555)
# Swap adjacent 2-bit groups
n = ((n & 0x33333333) << 2) | ((n >> 2) & 0x33333333)
# Swap adjacent 4-bit groups
n = ((n & 0x0f0f0f0f) << 4) | ((n >> 4) & 0x0f0f0f0f)
# Swap adjacent bytes
n = ((n & 0x00ff00ff) << 8) | ((n >> 8) & 0x00ff00ff)
# Swap adjacent 16-bit halves
n = ((n & 0x0000ffff) << 16) | ((n >> 16) & 0x0000ffff)
return n & 0xFFFFFFFF
# Verify against iterative version
def reverse_bits_iter(n):
result = 0
for _ in range(32):
result = (result << 1) | (n & 1); n >>= 1
return result
for test in [0b10110100, 0b11111111, 0, 1, 0xDEADBEEF]:
assert reverse_bits_dc(test) == reverse_bits_iter(test)
print(f'{test:#010x} reversed: {reverse_bits_dc(test):#010x}')1비트 개수(해밍 가중치)
1비트 개수 문제(LeetCode 191)는 부호 없는 정수의 해밍 가중치(1비트 개수)를 구하라고 합니다. 서로 다른 장단점을 가진 세 가지 방법이 있습니다. 순진한 반복문(O(32)), Brian Kernighan 방법(O(k), k = 설정된 비트 수), Python 내장 함수 n.bit_count()(3.10 이상)입니다.
Brian Kernighan 방법은 n & (n-1) 기법에 대한 이해를 보여 주므로 면접에서 선호됩니다. 각 반복에서 최하위 설정 비트를 제거하므로, 반복문은 1비트가 존재하는 횟수만큼만 정확히 실행됩니다. 따라서 성긴 정수에서는 32비트 전체를 검사하는 것보다 훨씬 빠릅니다.
def hamming_weight_naive(n):
count = 0
while n:
count += n & 1
n >>= 1
return count
def hamming_weight_kernighan(n):
count = 0
while n:
n &= n - 1 # clear lowest set bit
count += 1
return count
# Python 3.10+
# def hamming_weight_builtin(n): return n.bit_count()
for n in [0, 1, 11, 128, 255, 0xDEADBEEF]:
naive = hamming_weight_naive(n)
kern = hamming_weight_kernighan(n)
bits = bin(n).count('1')
print(f'{n:#012b} ({n:10d}): naive={naive}, kern={kern}, bin={bits}')연속 비트의 합: 접두사 합 접근법
때로는 [l, r] 범위에서 1비트의 개수를 빠르게 세어야 합니다. 0부터 n까지에 대한 설정 비트의 접두사 합을 만듭니다. prefix[i] = prefix[i-1] + bin(i).count('1')으로 계산할 수 있습니다. 그러면 [l, r] 범위의 개수는 prefix[r] - prefix[l-1]입니다. 이렇게 하면 O(n) 전처리 후 범위 질의를 O(1)에 처리할 수 있습니다.
이는 범위에 대한 모든 비트 기반 집계로 일반화할 수 있습니다. 예를 들어 [l, r]에서 설정된 비트 수가 짝수인 수를 세려면 동일한 접두사 기법을 사용하되 누적 함수를 다르게 지정하면 됩니다.
def build_bit_prefix(n):
prefix = [0] * (n + 2)
for i in range(1, n + 1):
prefix[i] = prefix[i - 1] + bin(i).count('1')
return prefix
def count_bits_range(prefix, l, r):
return prefix[r] - prefix[l - 1]
# Build prefix for 0..15
prefix = build_bit_prefix(15)
print('Prefix sums (set bit counts up to i):')
for i in range(16):
print(f' i={i:2d} ({bin(i)[2:]:4s}): bits={bin(i).count("1")}, prefix={prefix[i]}')
# Range queries
print(f'\nSet bits in [5, 10]: {count_bits_range(prefix, 5, 10)}')
print(f'Set bits in [1, 15]: {count_bits_range(prefix, 1, 15)}')음수의 비트 반전
Python의 정수는 부호가 있고 너비가 임의적입니다. LeetCode 문제에서 비트를 반전할 때는 입력을 32비트 부호 없는 정수로 취급해야 합니다. 처리하기 전에 입력에 & 0xFFFFFFFF를 적용하여 32비트만 고려하도록 합니다. 출력도 부호 없는 32비트 정수(음수가 아닌 값)여야 합니다.
2의 보수 관점에서 음수일 수 있는 Python 정수가 주어지면 먼저 & 0xFFFFFFFF를 적용해 부호 없는 32비트 표현을 얻은 다음 반전합니다. the 결과는 항상 0 이상 2^32 - 1 이하의 정수입니다.
def reverse_bits_signed_safe(n):
n &= 0xFFFFFFFF # treat as 32-bit unsigned
result = 0
for _ in range(32):
result = (result << 1) | (n & 1)
n >>= 1
return result & 0xFFFFFFFF
# Python treats -1 as all 1s in two's complement
print(f'-1 as 32-bit unsigned: {-1 & 0xFFFFFFFF:#010x}') # 0xffffffff
print(f'Reversed: {reverse_bits_signed_safe(-1):#010x}') # 0xffffffff (all 1s reversed = all 1s)
# -2 in 32-bit = 0xFFFFFFFE = 11...10
print(f'-2 as 32-bit unsigned: {-2 & 0xFFFFFFFF:#010x}') # 0xfffffffe
print(f'Reversed: {reverse_bits_signed_safe(-2):#010x}') # 0x7fffffff비트 조작 DP: 비트 개수 패턴 세기
비트 세기 문제는 비트 DP의 일반적인 패턴을 보여 줍니다. i의 더 작은 형태에 대한 답을 알고 있다면 상수 시간 비트 연산을 사용해 i에 대한 답을 계산할 수 있습니다. 이 패턴은 [0, n]에서 정확히 k개의 설정 비트를 가진 수 세기(이진 열거 사용) 또는 각 수를 나누는 가장 높은 2의 거듭제곱 구하기와 같은 다른 비트 세기 문제에도 일반화됩니다.
또 다른 유용한 관찰은 i의 설정 비트 개수가 각 2의 거듭제곱 구간에서 반복되는 패턴을 따른다는 것입니다. [2^k, 2^(k+1) - 1]의 패턴은 [0, 2^k - 1]의 패턴과 같고 각 값이 1씩 증가합니다. 이 구간에서는 비트 k가 항상 설정되어 있기 때문입니다.
# Visualise the repeating pattern
def show_bit_pattern(n):
bits = [bin(i).count('1') for i in range(n + 1)]
print('i | bits | pattern')
for i, b in enumerate(bits):
block = i.bit_length() - 1 if i > 0 else 0
print(f'{i:2d} ({bin(i)[2:]:4s}) | {b} | block {block}')
return bits
bits = show_bit_pattern(15)
# Verify the pattern: bits[i] = bits[i - highest_power] + 1 for i >= 2^k
print('\nVerify pattern:')
for i in range(1, 16):
highest_pow = 1 << (i.bit_length() - 1)
if highest_pow < i:
prev_i = i - highest_pow
print(f'bits[{i}] = bits[{prev_i}] + 1 = {bits[prev_i]} + 1 = {bits[i]}')세 가지 모두 결합하기: 통합 연습
많은 면접 문제는 비트 세기, 누락된 수에 대한 논리, 비트 반전을 하나의 문제로 결합합니다. 예를 들어 원소가 n비트 정수이고 그중 하나가 누락된 배열이 주어졌을 때 누락된 값을 찾는 문제입니다. 또는 비트 개수의 스트림이 주어졌을 때 누락된 정수를 복원하는 문제입니다. 이런 문제에서는 어떤 하위 기법을 적용해야 하는지 알아야 합니다.
머릿속 지도를 만들어 연습해 보십시오. 문제에서 누락된 원소를 찾으라고 하면 XOR 또는 합계를 떠올립니다. '1의 개수를 효율적으로 세라'고 하면 커니핸 방법 또는 DP를 떠올립니다. '비트를 반전하라'고 하면 반복 방법 또는 분할 정복을 떠올립니다. 이것이 면접에서 비트 조작에 사용하는 세 가지 핵심 도구입니다.
# Integrated exercise: given bit-count array, find the missing number
# arr[i] = number of 1 bits in i, for all i in 0..n except one
# Reconstruct the missing number
def find_missing_from_bit_counts(bit_counts, n):
# Rebuild full count array
full = [bin(i).count('1') for i in range(n + 1)]
# Find which index is missing by comparing
for i, count in enumerate(bit_counts):
if full[i] != count:
return i - 1 # the entry before the mismatch is missing
return n # last element missing
# Simpler: use XOR on indices matching bit counts
# (This is simplified for illustration)
bits = [0,1,1,2,1,2,2,3,0,1] # bit counts for 0..9 with 8 missing
# Normal: [0,1,1,2,1,2,2,3,1,2]
# Missing is index 8
full = [bin(i).count('1') for i in range(10)]
missing_idx = None
for i in range(10):
if i >= len(bits) or bits[i] != full[i]:
missing_idx = i
break
print(f'Missing number: {missing_idx}')비트 반전을 위한 캐싱
비트 반전을 반복해서 호출하는 경우(예: 하드웨어 시뮬레이션) 8비트 단위의 결과를 캐시에 저장하십시오. 각 바이트는 256개의 값만 가질 수 있으므로 0부터 255까지 각 값에 대해 반전된 바이트를 미리 계산합니다. 32비트 정수를 반전하려면 네 개의 8비트 단위로 나누고, 각 단위를 반전한 다음 순서를 반대로 하여 다시 결합합니다.
이렇게 하면 각 호출이 네 번의 테이블 조회와 비트 연산으로 줄어들어, 대량 처리에서 32회 반복문보다 훨씬 빠릅니다. the 캐시는 O(256 × 8) 시간에 한 번 구축하고 이후 모든 호출에서 O(1)로 재사용합니다.
# Build 8-bit reverse cache
def build_reverse_byte_cache():
cache = [0] * 256
for i in range(256):
n, result = i, 0
for _ in range(8):
result = (result << 1) | (n & 1)
n >>= 1
cache[i] = result
return cache
cache = build_reverse_byte_cache()
def reverse_bits_cached(n):
return (cache[n & 0xFF] << 24 |
cache[(n >> 8) & 0xFF] << 16 |
cache[(n >> 16) & 0xFF] << 8 |
cache[(n >> 24) & 0xFF])
# Test
for test in [0b10110100, 0b11111111, 0x12345678]:
cached = reverse_bits_cached(test)
# Reference: iterative
n, result = test, 0
for _ in range(32): result = (result << 1) | (n & 1); n >>= 1
assert cached == result
print(f'{test:#010x} => {cached:#010x}')빠른 확인
이 단원에서 다룬 자료 구조 및 알고리즘 — 코딩 면접 준비 개념에 대한 이해도를 확인해 보십시오.
단원 요약
이 단원에서 배운 내용은 다음과 같습니다. 비트 세기는 dp[i] = dp[i >> 1] + (i & 1) 또는 dp[i] = dp[i & (i-1)] + 1인 DP를 사용하므로 O(n) 시간이 걸립니다. 누락된 수는 모든 인덱스를 모든 값과 XOR하거나 산술 합계 공식을 사용하여 O(n)/O(1)에 해결할 수 있습니다. 32비트 반전은 O(32)의 반복 방법이나 분할 정복 마스크 기법으로 수행할 수 있습니다. 다음으로는 증가 불변식과 감소 불변식을 비교하고 다음으로 큰 원소 질의를 살펴보는 것부터 단조 스택을 알아봅니다.
자주 묻는 질문
“비트 세기, 누락된 숫자와 비트 뒤집기” 강의는 무료인가요?
네 — “비트 세기, 누락된 숫자와 비트 뒤집기” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“비트 세기, 누락된 숫자와 비트 뒤집기”에서 뭘 배우나요?
DP와 최하위 설정 비트 기법으로 0부터 n까지의 비트 개수를 계산하고, XOR로 누락된 숫자를 찾으며, 32비트 정수의 비트를 뒤집습니다. 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 4번째 강의입니다.
“비트 세기, 누락된 숫자와 비트 뒤집기” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 비트 연산자: AND, OR, XOR, NOT, 시프트
- 단일 숫자와 XOR의 성질
- 비트 마스크: 설정, 해제, 전환, 확인
- 비트 세기, 누락된 숫자와 비트 뒤집기