[알고리즘] 프로그래머스 : 연속 부분 수열 합의 개수 Lv. 2

에서 GPT 로 수행 시간을 줄이는 실험을 하던 도중 새롭게 알게된 자료구조 BitSet 에 대해 설명한다.

BitSet

• BitSet은 자바에서 비트 단위로 값을 저장하고 처리하는 자료 구조입니다.

• 각 비트는 true(1) 또는 false(0)의 두 가지 값을 가집니다.

• BitSet은 일반적으로 대량의 이진 데이터를 효율적으로 저장하기 위해 사용됩니다.

  가변 길이 비트 벡터를 나타내므로 크기(size)라는 개념이 명시적으로 정의되어 있지 않습니다. BitSet은 사용 중인 비트의 범위를 동적으로 확장하므로 크기를 미리 정할 필요가 없습니다. 즉, BitSet의 크기는 동적으로 조절됩니다.
  따로 초기화시에 size를 지정하지 않았다면 default size 는 64 입니다.

BitSet 클래스의 주요 특징과 사용법은 다음과 같습니다:

비트 설정 및 해제

• set(int bitIndex): 주어진 비트 인덱스를 1(true)로 설정합니다.
• clear(int bitIndex): 주어진 비트 인덱스를 0(false)로 설정합니다.

비트 조회

• get(int bitIndex): 주어진 비트 인덱스의 값을 반환합니다.

비트 조작

• and(BitSet set): 현재 BitSet 객체와 다른 BitSet 객체 간의 AND 연산을 수행합니다.
• or(BitSet set): OR 연산을 수행합니다.
• xor(BitSet set): XOR 연산을 수행합니다.

카디널리티(비트가 1인 비트 수) 계산

• cardinality(): 비트가 1인 비트의 수를 반환합니다.

비트 연산

• andNot(BitSet set): 현재 BitSet 객체에서 다른 BitSet 객체의 비트를 제거합니다.

범위 설정 및 조회

• set(int fromIndex, int toIndex): 주어진 범위의 비트를 1(true)로 설정합니다.
• get(int fromIndex, int toIndex): 주어진 범위의 비트 값을 반환합니다.

직렬화 및 역직렬화

• toByteArray(): BitSet을 바이트 배열로 변환합니다.
• valueOf(byte[] bytes): 바이트 배열을 BitSet으로 변환합니다.

BitSet은 주로 대량의 이진 데이터를 효율적으로 저장하고 다룰 때 유용합니다.
여러 비트를 한 번에 처리할 수 있기 때문에 메모리 사용량이 낮고 연산이 빠릅니다.
이러한 특성은 특히 대규모 데이터 집합에서 중복을 확인하는데 유용할 수 있습니다.

오라클 자바8 BitSet 공식문서

설명에 따르면

BitSet 은 기본적으로 long Array 64 의 size 를 갖는다.

[00000000, 00000000, 00000000, 00000000,
 00000000, 00000000, 00000000, 00000000]

위 구조를 인덱스로 알아보기 쉽게 표현해보자면

[7 6 5 4 3 2 1 0, 15 14 13 12 11 10 9 8, ........, ........, ........, ........, ........, 64.......]
 		 0   				1        		2         3         4           5        6        7

이렇게 생성된 배열은 0 또는 1의 값을 가진다.

따라서 set(7) 의 결과는 다음과 같다.

[10000000, 00000000, 00000000, 00000000,
 00000000, 00000000, 00000000, 00000000]

이를 통해 0 이상의 정수를 중복 없는 데이터로 가볍게 관리할 수 있다.