32비트 정수에서 설정된 비트 수를 세는 알고리즘
순차적 검사:
가장 간단한 방법은 모든 비트를 순차적으로 검사하여 1인 비트를 카운트하는 것입니다. 다음은 C++ 코드 예시입니다.
int countSetBits(int n) {
int count = 0;
for (int i = 0; i < 32; i++) {
if ((n >> i) & 1) {
count++;
}
}
return count;
}
이 알고리즘은 O(n) 시간 복잡도를 가지고 있으며, 모든 비트를 검사하기 때문에 비교적 느립니다.
Brian Kernighan의 알고리즘:
Brian Kernighan은 다음과 같은 더 효율적인 알고리즘을 제안했습니다.
int countSetBits(int n) {
int count = 0;
while (n) {
n &= (n - 1);
count++;
}
return count;
}
이 알고리즘은 n을 n-1과 비트별로 AND 연산한 후 1로 설정된 비트 수를 세웁니다. 이 과정을 n이 0이 될 때까지 반복합니다. 이 알고리즘은 O(log n) 시간 복잡도를 가지고 있으며, 앞서 소개한 순차적 검사 알고리즘보다 훨씬 빠릅니다.
PopCount 함수 사용:
일부 프로그래밍 언어는 popcount()과 같은 내장 함수를 제공하여 32비트 정수에서 설정된 비트 수를 빠르게 세는 데 사용할 수 있습니다. 예를 들어, 다음은 C 언어의 popcount() 함수를 사용하는 예시입니다.
int countSetBits(int n) {
return _popcnt(n);
}
이러한 내장 함수는 일반적으로 하드웨어 지원을 사용하기 때문에 매우 빠릅니다.
비트 마스킹:
비트 마스킹을 사용하여 특정 비트 범위에서 설정된 비트 수를 세는 방법도 있습니다. 예를 들어, 다음은 하위 8비트에서 설정된 비트 수를 세는 C++ 코드입니다.
int countSetBits(int n) {
int mask = 0xFF;
return (n & mask) * 0x01;
}
이 코드는 0xFF 마스크를 사용하여 하위 8비트만 1로 설정하고, AND 연산을 사용하여 해당 비트만 n 값에 남겨둡니다. 마지막으로 0x01을 곱하여 결과 값을 얻습니다.
이처럼 32비트 정수에서 설정된 비트 수를 세는 데에는 여러 가지 방법이 있습니다. 각 방법마다 장단점이 있으므로, 특정 상황에 가장 적합한 방법을 선택해야 합니다.
관련 알고리즘
추가 정보
32비트 정수에서 설정된 비트 수를 세는 예제 코드
C++:
#include <iostream>
using namespace std;
int countSetBits(int n) {
int count = 0;
while (n) {
n &= (n - 1);
count++;
}
return count;
}
int main() {
int n;
cout << "32비트 정수 입력: ";
cin >> n;
int setBits = countSetBits(n);
cout << n << "에는 " << setBits << "개의 설정된 비트가 있습니다." << endl;
return 0;
}
Python:
def count_set_bits(n):
count = 0
while n:
n &= (n - 1)
count += 1
return count
n = int(input("32비트 정수 입력: "))
set_bits = count_set_bits(n)
print(f"{n}에는 {set_bits}개의 설정된 비트가 있습니다.")
Java:
public class CountSetBits {
public static int countSetBits(int n) {
int count = 0;
while (n > 0) {
n &= (n - 1);
count++;
}
return count;
}
public static void main(String[] args) {
int n = Integer.parseInt(System.in.readLine("32비트 정수 입력: "));
int setBits = countSetBits(n);
System.out.println(n + "에는 " + setBits + "개의 설정된 비트가 있습니다.");
}
}
JavaScript:
function countSetBits(n) {
let count = 0;
while (n) {
n &= (n - 1);
count++;
}
return count;
}
const n = parseInt(prompt("32비트 정수 입력: "));
const setBits = countSetBits(n);
console.log(`${n}에는 ${setBits}개의 설정된 비트가 있습니다.`);
이 코드들은 모두 동일한 기능을 수행하지만, 각 프로그래밍 언어의 구문 및 표현 방식에 따라 다소 차이가 있습니다.
코드를 실행하면 사용자로부터 32비트 정수를 입력받고, 해당 정수에서 설정된 비트 수를 계산하여 출력합니다.
추가 예제
- 특정 비트 범위에서 설정된 비트 수를 세는 코드:
int countSetBitsInRange(int n, int l, int r) {
int mask = (1 << r) - 1; // 범위 내 1로 설정된 비트 마스크 생성
n &= mask; // n 값을 마스크와 AND 연산하여 범위 내 비트만 남김
return countSetBits(n); // 위 코드를 사용하여 설정된 비트 수 계산
}
- 내장 함수 사용 예제 (popcount() 함수가 있는 경우):
int countSetBits(int n) {
return __builtin_popcount(n); // popcount() 함수 사용
}
32비트 정수에서 설정된 비트 수를 세는 대체 방법
분할 정복:
다음은 분할 정복 기법을 사용하는 알고리즘입니다.
int countSetBits(int n) {
if (n == 0) {
return 0;
}
int half = n >> 1; // 정수를 절반으로 나눔
int count = countSetBits(half); // 절반 값에서 설정된 비트 수 계산
// 하위 비트는 절반 값과 동일하므로, 상위 비트만 확인
if (n & 1) {
count++; // 1로 설정된 상위 비트 1개 추가
}
return count;
}
이 알고리즘은 n을 절반으로 나누고, 각 절반에서 설정된 비트 수를 재귀적으로 계산합니다.
루프 최적화:
Brian Kernighan의 알고리즘을 다음과 같이 루프를 최적화하여 속도를 향상시킬 수 있습니다.
int countSetBits(int n) {
int count = 0;
while (n) {
n &= (n - 1); // n 값을 n-1과 비트별로 AND 연산
count++;
}
// 루프 최적화
int trailingOnes = 0;
int p = 1; // 2^0 = 1
while ((n & p) == 0) {
p <<= 1; // 다음 비트 위치로 이동
trailingOnes++;
}
// 마지막으로 trailingOnes 개의 1을 추가
count += trailingOnes;
return count;
}
이 알고리즘은 루프의 마지막 부분에서 n 값이 0이 될 때까지 연속적으로 1로 설정된 비트 수를 카운트합니다.
루크 테이블 사용:
const int table[16] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
int countSetBits(int n) {
int count = 0;
while (n) {
count += table[n & 15]; // 하위 4비트에서 설정된 비트 수 테이블에서 가져옴
n >>= 4; // 다음 4비트 위치로 이동
}
return count;
}
이 알고리즘은 0~15까지의 모든 숫자에 대해 설정된 비트 수를 미리 계산하여 테이블에 저장하고, 4비트 단위로 테이블 값을 사용하여 전체 설정된 비트 수를 계산합니다.
하드웨어 지원:
일부 CPU는 특정 비트 연산을 위한 하드웨어 지원을 제공합니다. 예를 들어, SSE (Streaming SIMD Extensions) 명령어 집합은 popcnt 명령어를 제공하여 32비트 정수에서 설정된 비트 수를 빠르게 계산할 수 있습니다.
#include <immintrin.h>
int countSetBits(int n) {
return _mm_popcnt_u32(n); // SSE 명령어 사용
}
이러한 하드웨어 지원을 활용하면 코드 속도를 크게 향상시킬 수 있습니다.
선택 및 비교
각 방법마다 장단점이 있으며, 특정 상황에 가장 적합한 방법을 선택해야 합니다.
- Brian Kernighan의 알고리즘: 간단하고 이해하기 쉬우며, 대부분의 경우 충분히 빠릅니다.
- 분할 정복: 더 빠른 속도를 제공할 수 있지만, 코드가 다소 복잡합니다.
- 루프 최적화: Brian Kernighan의 알고리즘보다 빠른
algorithm binary bit-manipulation
