정의
비트 벡터(Bit vector, bitset)는 고정된 길이의 0과 1로 구성된 배열을 의미한다. 각 원소는 단일 비트를 차지하며, 인덱스를 통해 개별 비트에 접근하고 수정할 수 있다. 일반적으로 이진 상태(예: 포함 여부, 사용 여부)를 효율적으로 표현하고 집합 연산을 수행하기 위해 사용된다.
주요 특성
- 저장 효율성: 한 비트당 1비트만 사용하므로 대규모 논리 집합을 압축된 형태로 저장할 수 있다.
- 상수 시간 연산: 비트 단위 연산(AND, OR, XOR, NOT 등)은 하드웨어 레벨에서 대부분 O(1) 시간에 수행된다.
- 고정 길이: 초기 생성 시 길이가 지정되며, 일반적인 구현에서는 동적으로 크기를 변경하지 않는다.
대표적인 연산
| 연산 | 설명 |
|---|---|
set(i) |
i번째 비트를 1로 설정 |
reset(i) |
i번째 비트를 0으로 설정 |
flip(i) |
i번째 비트를 토글 |
test(i) |
i번째 비트가 1인지 여부 반환 |
count() |
전체 비트 중 1인 비트의 개수 반환 |
any() |
1인 비트가 하나라도 존재하는지 여부 반환 |
none() |
모든 비트가 0인지 여부 반환 |
operator&(다른 비트 벡터) |
비트 단위 AND 연산 결과 반환 |
| `operator | (다른 비트 벡터)` |
operator^(다른 비트 벡터) |
비트 단위 XOR 연산 결과 반환 |
활용 사례
- 집합 표현: 특정 범위의 정수를 포함 여부를 비트로 나타내는 경우 (예: 해시 충돌 회피, 비트맵 인덱스).
- 플래그 저장: 여러 독립적인 상태를 하나의 정수형 변수에 압축 저장 (예: 파일 권한, 옵션 플래그).
- 그래프 알고리즘: 방문 여부나 인접 행렬 대체 등에서 메모리 사용을 최소화.
- 압축 데이터 구조: 라디컬(라디컬) 트리, 세그먼트 트리와 결합해 비트 레벨 검색 및 업데이트를 지원.
표준 라이브러리 지원
C++ 표준 라이브러리에서는 std::bitset<N>이 고정 길이 비트 벡터를 제공한다. Java에서는 java.util.BitSet이 가변 길이 비트 벡터 구현을 제공한다. Python에서는 int 타입을 비트 연산에 활용하거나 bitarray 외부 패키지를 사용한다.
제한 사항
- 고정 길이: 초기 길이 지정 후에는 일반적인 구현에서 확대가 불가능하므로, 사용 목적에 맞는 크기를 사전에 판단해야 한다.
- 스레드 안전성: 비트 단위 연산이 원자적(atomic)이지 않을 수 있어, 다중 스레드 환경에서는 동기화가 필요하다.
관련 개념
- 비트 마스크: 특정 비트만을 선택하거나 변형하기 위해 사용되는 상수 값.
- 비트 배열(bit array): 비트 벡터와 동일한 의미로 사용되는 경우가 많다.
- 루프 업(lookup) 테이블: 비트 패턴을 미리 계산해 빠른 변환을 지원한다.
참고 문헌
- C++ 표준 라이브러리 문서,
std::bitset - Java SE API 문서,
java.util.BitSet - Donald Knuth, The Art of Computer Programming, Volume 4, Fascicle 1 (Bitwise Operations)
본 문서는 확인된 자료에 근거하여 객관적·중립적으로 서술하였다.
