Bitset 자료구조란

Bitset이란

BitSet은 비트를 효율적으로 저장하고 조작할 수 있는 자료구조입니다.

Bitset 사용 이유

1. 메모리 효율

• boolean[]은 실제로는 한 요소당 1바이트 이상 사용되지만,BitSet은 64개의 비트를 long 1개에 담아 8바이트로 처리합니다.
• 👉 즉, 대량의 true/false 값을 다룰 때 훨씬 가볍습니다.

2. 성능

• 비트 연산 (|, &, ^)을 통해 대량의 boolean 값을 한 번에 계산할 수 있어 빠릅니다.
• 예: bitset1.and(bitset2) → 배열 전체를 순회하면서 동시에 AND 처리

3. 개발자 실수 줄여줌

• Java는 정수 타입을 이용한 직접적인 비트 연산보다 BitSet을 사용할 때 더 읽기 쉽고 안전한 코드를 작성할 수 있게 해줍니다.
• 컴파일러가 bitIndex 음수 체크, 범위 체크 등을 도와주므로 런타임 에러 발생 가능성도 줄어듭니다.
• set, clear, get 같은 명확한 API 제공으로 직접 비트 마스킹하면서 생길 수 있는 실수를 줄여줍니다.

BitSet은 어떻게 비트를 저장할까?

• BitSet은 long[] 배열을 씁니다.
• long = 64비트 (즉, 64개의 true/false 비트 값을 저장 가능)
• Default,long 요소 한개

---

핵심 메소드

연산	연산자	목적
set	|=	1로 만들기
get	&	값 확인
clear	&= ~	0으로 만들기
flip	^=	0이면 1로, 1이면 0으로 변경

set 함수

• wordIndex(bitIndex)를 이용해 해당 비트가 저장될 long의 위치를 찾습니다.
• 1L << bitIndex는 해당 비트 위치에 1을 만들어줍니다.
• |= 연산은 기존 값에 1을 OR 해서 해당 위치만 1로 바꿔줍니다.

wordIndex 함수의 역할은 무엇인가요?

가령 100번째 비트를 바꾼다고 하면, 100번째 비트는 long[] 배열의 몇 번째 원소에 들어가야 할까요?

하나의 long에 64개의 비트를 넣을 수 있으니까,

0번째 long: 0 ~ 63번째 비트
1번째 long: 64 ~ 127번째 비트

100번째 비트는 64보다 크고 127보다 작으니 1번째 long에 저장되어야 합니다.

그런데 왜 /64 대신  >> 6을 쓰나요?

/ 64는 산술 나눗셈입니다. 하지만 컴퓨터에서는 2의 거듭제곱으로 나누는 것은 훨씬 빠르게 계산할 수 있습니다.

64는 2의 6 제곱입니다. 즉, bitIndex / 64는 bitIndex >> 6과 같습니다.

(x >> n은 2ⁿ으로 나눈 몫을 계산하는 것과 같습니다.)