비트셋(BitSet)

배열(Array)다음에 링크드리스트(LinkedList)를 이어서 설명하려 하였으나 비트셋이 배열 다음으로 어울릴것 같아서 비트셋(Bitset)부터 먼저 설명하려고한다. 

우리가 SW를 만들(또는 구현)때 가장 많이 고려해야 할 것들은 무엇일까?

개인마다 차이는 있겠지만 아래의 것들을 고려해야 해야 한다는 것에 어느정도 공감할 것이다.

 

1. 퍼포먼스가 좋고. 즉, 속도가 빠르고

2. 메모리(=리소스)를 적게 사용하고

3. 버그는 없으며

4. 코드는 간결하고 

5. 유지보수는 쉽고  확작성은 열려있게  설계해야 하고

6. 가독성(Readability)도 좋고

7. 오픈소스로 제공하면 좋고 ... 공짜면 더 좋고 ^^

.. 등등 ...

 

그런데 보통 SW작성시 1번과 2번은 대부분 대립각을 세운다. 

즉, 퍼포먼스(속도)를 더 빠르게 하려면 메모리를 더 사용해야 하고 메모리를 적게 사용하려면 속도의 최적화가 힘들어지는 경우가 종종 발생된다. 왜 이런 얘기를 하는가 하면 bitset 은 특정 자료를 저장하기 위해 메모리를 최적화하여 사용하는 자료구조이기 때문이다. 

물론 속도도 비트연산(bit operation)을 하기 때문에 빠르다. 

 

그럼 특정 자료란 무엇인가?

이름에서 유추하면 bit ( 비트는 0과 1만 저장할수 있는 컴퓨터에서 데이터를 나타내는 최소 단위)를 set(설정) 하기 위한 자료구조이다. 

간단히 bit (0과 1)을 R/W 하기 위한 방법이 구나 생각하면 된다. 

근데 0 과 1은 어떤 의미일까? 0과 1을 어떻게 사용할 수 있을까? 생각하면  0 = false로 1=true로 생각할 수 있다. 

따라서 참과 거짓을 저장할 필요가 있는 경우면 bitset을 사용하면된다. 

 

이런 용도를 위한 것으로 자바에서는 BitSet , C++ 에서는 stl::bitset 이 built-in 되어 있다. 

// 64개의 참과 거짓을 저장 할 수 있다.
BitSet bitset = new BitSet(32);
 
// 0, 1번 인덱스를 true로 (내부적으로는 0, 1번째 bit를 1로 설정)
bitset.set(0);
bitset.set(1);
System.out.println(bitset.get(0));
System.out.println(bitset.get(1));
 
// 1번 인덱스를 false 로
bitset.clear(1);
System.out.println(bitset.get(1));

근데 갑자기 이런 의문이 들것이다. 

true, false 를 저장할 것이면 배열로도 가능하지 않느냐 ? 맞다 가능하다.

 

        
List<Boolean> arr = new ArrayList<>();
arr.add(true);
arr.add(true);
 
System.out.println(arr.get(0));
System.out.println(arr.get(1));
 
arr.set(1, false);
System.out.println(arr.get(1));
 
// Boolean은 class 말고 primitive 타입인 boolean 을 배열로 해서 처리도 가능
 
boolean []arr = new boolean[32];
arr[0] = true;
arr[1] = true;
 
System.out.println(arr[0]);
System.out.println(arr[1]);
 
arr[1] = false;
System.out.println(arr[1]);
 

출력은 모두 동일하다. 그럼 왜 bitset 이 있는것인가 ? 위에서 bitset 은 특정 자료를 저장하기 위해 메모리를 최적화하여 사용하는 자료구조라고 얘기했다. boolean 은 메모리를 얼마나 차지하는지 아는가 ? 바로 8bit( 1byte) 이다. 

64개를 저장하기위해 필요한 메모리가 32bytes 가 필요한것이다.

true, false 2가지만 저장하는데 너무 많은 bit를 자치하고 있는것처럼 보이지 않는가 ? 

0 -> false로, 1 -> true로 할수 있다면 0, 1 2개만 저장할 bit 만 있으면 충분해 보이지 않는가 ?

그렇다. bitset 은 true, false 를 위해 1bit만 사용한다. 

 

그럼 integer -> 4bytes 이고 -> 32bit이니 하나의 integer 에 32개의 true, false를 저장할수 있는 공간이 생긴다. 

 

32개를 저장해야하면 integer 1개

64개를 저장해야하면 integer 2개 (new integer[2]) 가 필요할 것이고

96개는 3개(new integer[3]) 만 있으면된다. 

 

배열자체가 랜덤 엑세스가 가능하고 각 정수형에 bit 접근은  비트연산 & (and), | (or) 와 shift ( >>, <<) 만 있으면 된다.

 

예를들어보자. 32개의 bit를 저장하기위해 integer 하나를 선언

 

integer i = 4bytes = 0xffffffff = 32bits = (00000000)(00000000)(00000000)(00000000) <- 가독성을 위해 1byte씩 ()로 그룹핑했다.

 

첫번째를 1로 설정하기위해서 0x00000001 를  | (or 연산한다.)

(00000000)(00000000)(00000000)(00000000)  | (00000000)(00000000)(00000000)(00000001) 

두번째를  1로 설정하기위해서 0x0000010 를  | (or 연산한다.)

(00000000)(00000000)(00000000)(00000001) | (00000000)(00000000)(00000000)(00000010)

두번째를 0으로 다시 설정하기위해서 0x0000010 의 ~(not 연산) -> oxfffffff2 를 & 연산한다.

(00000000)(00000000)(00000000)(00000011) | (11111111)(11111111)(11111111)(11111101)

 

이걸 공식처럼 적용하면 아래처럼 되고 공식을 이용하여 위 코드를 다시 작성하면  다음과 같다.

 

▷ 해당 비스트를 1로 설정 : i  |= (1L << bitIndex); 

▷ 해당 비스트를 0으로 설정 i &= ~(1L << bitIndex);

▷ 해당비트가 1이니 0인지 엑세스 : i & (1L << bitIndex)

 

비트 연산이 어려우면  VisuAlgo - Bitmask : https://visualgo.net/ko/bitmask 로 가서 비트연산을 시물레이션해 보면서 개념을 익히면 좋다.

int i = 0;
i |= (1L << 0); // 0번째 true
i |= (1L << 1); // 1번째 true
 
System.out.println( (i & (1L << 0)) > 0 ? true : false);
System.out.println( (i & (1L << 1)) > 0 ? true : false);
 
i &= ~(1L << 1); // 1번째 false
System.out.println( (i & (1L << 1)) == 1 ? true : false);

 

레퍼런스

• VisuAlgo - Bitmask : https://visualgo.net/ko/bitmask