Bit
개념
- 컴퓨터에서 비트(bit)는 0 또는 1의 값을 가지는 가장 작은 단위다.
- 여러 개의 비트가 모여 바이트(Byte), 워드(Word) 등을 구성
기본 문법 및 예시
- (& : AND)
-> 1100 & 0110 : 0100 - (| : OR)
-> 1100 | 0110 : 1110 - (^ : XOR)
-> 1100 ^ 0110 : 1010 - (~ : NOT)
-> ~1100 : 0011 - (<< : Left Shift)
-> 1100 << 1 : 11000 - (>> : Right Shift)
-> 1100 >> 1 : 110 - (>>> : 부호 없이 Right Shift)
-> 1100 >>> 1 : 0110
비트 연산을 알고리즘에서 사용하는 이유
- 비트 연산은 CPU 수준에서 수행
- 매우 빠름
- 메모리도 훨씬 적게 사용
Bit Masking
개념
- 비트마스킹은 하나의 정수형 변수(int, long 등)에 여러 상태를 저장
- 각 비트는 하나의 플래그(flag)를 의미, 비트 연산을 통해 값을 설정하거나 확인
장단점
장점
- 메모리 사용이 매우 적음 (비트 단위)
- 연산 속도가 매우 빠름 (O(1))
단점
- 범위가 크면 long으로도 부족함
- 가독성이 낮고, 디버깅이 어려움
활용할 때
- 32개 이하의 상태라면 int 하나로 충분
- 64개까지는 long, 그 이상은 BitSet 고려
문제를 활용한 사용 예시
- 가르침 : https://www.acmicpc.net/problem/1062
- 알파벳에 중복여부를 비트마스킹으로 check
- 성곽 : https://www.acmicpc.net/problem/2234
- 벽을 비트마스킹으로 setting
Bit Set
개념
- Java의 java.util.BitSet은 가변 크기의 비트 배열을 제공하는 표준 클래스
- 내부적으로 long 배열을 사용, 인덱스로 각 비트를 다룸
기본 문법 및 예시
// 생성
BitSet bs1 = new BitSet(); // 기본크기
BitSet bs2 = new BitSet(1000000); // 초기 크기 지정
// 선택 설정
bs1.set(5); // 5번 비트를 1로 설정
bs1.clear(5); // 5번 비트를 0으로 설정
bs1.flip(5); // 5번 비트를 반전 (0이면 1, 1이면 0)
// 전체 설정
bs1.clear(); // 전체 비트를 0으로 초기화
bs1.flip(0, 10); // 0번부터 9번까지 비트를 반전
// 조회
boolean on = bs1.get(5); // 5번 비트가 켜져 있는지 확인
// 논리연산
bs1.and(bs2); // AND 연산 (교집합)
bs1.or(bs2); // OR 연산 (합집합)
bs1.xor(bs2); // XOR 연산 (차집합)
bs1.andNot(bs2); // 차집합 a - b
int i = bs1.nextSetBit(0); // 0번 인덱스부터 처음 1인 비트 위치
int cardinality = bs1.cardinality(); // 켜진 비트의 수
int length = bs1.length(); // 가장 높은 1비트 + 1 위치
int size = bs1.size(); // 내부 배열의 크기 (최대 인덱스 아님)장단점
장점
- 크기 제약 없이 수백만 개 상태 표현 가능
- Java 표준 API로 사용이 직관적이고 안정적
- HashSet보다 훨씬 적은 메모리 사용
단점
- 비트마스킹보다 다소 느릴 수 있음
- synchronized가 아니므로 멀티스레드 환경에 주의 필요
활용할 때
- 데이터가 수천~수백만 개 이상이면서 중복 여부만 체크할 때
- 비트마스킹보다 범용성이나 가독성이 중요할 때
문제를 활용한 사용예시
- 중복제거 : https://www.acmicpc.net/problem/13701
- BitSet을 활용해서, 중복없이 순서에 맞춘 출력 구현
HashSet vs 비트마스킹 vs BitSet
| 방법 | 메모리 사용량 | 처리 속도 |
|---|---|---|
| HashSet | 높음 | 느림 |
| BitSet | 낮음 | 빠름 |
| 비트마스킹 | 가장 낮음 | 가장 빠름 (단 범위 제한 있음) |
Backend Developer