비트 개수와 최하위 설정 비트
popcount와 n & -n 기법을 사용합니다
비트 개수와 최하위 설정 비트은(는) CoddyKit의 무료 Competitive Programming Academy 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Competitive Programming Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
1 비트 세기
많은 문제에서는 수에서 설정된 비트가 몇 개인지 묻는데, 이를 해당 수의 1 비트 개수라고 합니다. 부분집합의 크기, 홀짝성 확인, 점수 계산 등에 활용됩니다. 🔢
Python의 내장 개수 세기
설정된 비트를 세는 가장 빠른 방법은 정수 메서드 bit_count()를 사용하는 것입니다. 반복문도 필요 없고 복잡하지도 않으며, 1의 개수만 바로 얻을 수 있습니다.
print((13).bit_count()) # 0b1101 has 3 onesbin과 count로 세기
bit_count를 잊었다면 수를 이진 텍스트로 바꾸고 1의 개수를 세면 됩니다. 더 느리지만 명확하고 기억하기 쉽습니다.
print(bin(13).count('1')) # 3가장 낮은 위치의 설정 비트
가장 낮은 위치의 설정 비트는 수에서 가장 오른쪽에 있는 1입니다. 이 비트를 분리하는 방법은 이후 펜윅 트리와 부분집합 기법에서 핵심적으로 사용됩니다.
n과 -n으로 분리하기
유명한 기법인 n & -n은 가장 낮은 위치의 설정 비트만 남깁니다. 2의 보수 표현에서 음수가 작동하는 방식 덕분에 마법처럼 동작합니다.
n = 12 # 0b1100
print(n & -n) # 4 = 0b100n과 -n이 작동하는 이유
부호를 반전하면 모든 비트가 뒤집힌 뒤 1이 더해지므로, 가장 낮은 1 아래에 있는 모든 비트가 반전됩니다. AND 연산을 하면 해당 비트 하나만 남습니다.
가장 낮은 설정 비트 제거하기
1을 빼면 끝에 이어진 0들을 거쳐 빌림이 발생하므로 n & (n - 1)은 가장 낮은 설정 비트를 지웁니다. 이 과정을 반복하면 1을 하나씩 제거할 수 있습니다.
n = 12 # 0b1100
print(n & (n - 1)) # 8 = 0b1000Brian Kernighan의 개수 세기
수가 0이 아닐 동안 반복하면서 매번 가장 낮은 비트를 지웁니다. 반복 횟수는 설정된 비트 수와 같으므로, 1 비트 개수가 적은 경우 빠릅니다.
c = 0
while n:
n &= n - 1
c += 12의 거듭제곱인지 확인하기
양의 2의 거듭제곱은 설정된 비트가 정확히 하나이므로 n & (n - 1)은 0이 됩니다. AND 연산 한 번으로 즉시 확인할 수 있습니다.
def is_pow2(n):
return n > 0 and (n & (n - 1)) == 0비트 개수로 홀짝성 구하기
수의 홀짝성은 1 비트 개수를 2로 나눈 나머지일 뿐입니다. 1의 개수가 홀수인지 짝수인지 한 단계로 확인할 수 있습니다.
parity = (13).bit_count() & 1 # 1가장 빠른 도구 선택하기
순수한 속도가 필요하면 bit_count를 사용하고, 설정된 비트를 순회하려면 n & (n-1) 반복문을 사용하세요. 알맞은 도구를 선택하면 엄격한 시간 제한도 만족할 수 있습니다. ⚡
빠른 확인
가장 낮은 위치의 설정 비트 기법을 확인하세요.
복습: 비트 세기
bit_count로 1의 개수를 세고, n & -n으로 가장 낮은 비트를 분리하며, n & (n-1)로 해당 비트를 제거할 수 있습니다. 강력한 한 줄 표현들입니다. 🎉
자주 묻는 질문
“비트 개수와 최하위 설정 비트” 강의는 무료인가요?
네 — “비트 개수와 최하위 설정 비트” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Competitive Programming Academy 강의 전체를 잠금 해제할 수 있습니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“비트 개수와 최하위 설정 비트”에서 뭘 배우나요?
popcount와 n & -n 기법을 사용합니다 브라우저에서 직접 실행하는 실습 코드로 Competitive Programming Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Competitive Programming Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Competitive Programming Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.
“비트 개수와 최하위 설정 비트” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Competitive Programming Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Competitive Programming Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- AND, OR, XOR와 시프트
- 비트 설정, 삭제와 토글
- 비트 개수와 최하위 설정 비트
- 작은 집합으로 사용하는 비트마스크