자바와 비트마스크, BitSet

자바에는 비트마스크에 관한 라이브러리가 있는데,

java.util.BitSet 클래스가 바로 그것이다.

 

이전 글까지만 해도 직접 구현하였다.

만약 실무에 써먹을 일이 있다면

(적어도나는) 요 라이브러리를 써먹을 것이다.

하나씩 알아보자.

 

 

 

 

/*
* BitSets are packed into arrays of "words."  Currently a word is
* a long, which consists of 64 bits, requiring 6 address bits.
* The choice of word size is determined purely by performance concerns.
*/
private final static int ADDRESS_BITS_PER_WORD = 6;
private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
private final static int BIT_INDEX_MASK = BITS_PER_WORD - 1;

/**
* The internal field corresponding to the serialField "bits".
*/
private long[] words;

/**
* The number of words in the logical size of this BitSet.
*/
private transient int wordsInUse = 0;

/**
* Whether the size of "words" is user-specified.  If so, we assume
* the user knows what he's doing and try harder to preserve it.
*/
private transient boolean sizeIsSticky = false;

 

 

 

생성자의 파라미터가 없는 경우, BITS_PER_WORD의 값(100 0000, 64)을 initWords의 인자로 준다.

그리고 wordIndex는 파라미터를 왼쪽 시프트 연산을 ADDRESS_BITS_PER_WORD의 값(6)만큼해주는데..

64-1 >> 6의 결과는 0 이므로 BitSet의 필드 words에는 크기가 1인 long배열이 할당된다.

 

생성자의 파라미터값이 65일 경우,

65-1 >> 6의 결과는 1 이므로 BitSet의 필드 words에는 크기가 2인 long배열이 할당된다.

∴

생성자의 파라미터값이 129일 경우,

129-1 >> 6의 결과는 2 이므로 BitSet의 필드 words에는 크기가 3인 long배열이 할당된다.

 

wordIndex 메소드가 받아온 파라미터나 BITS_PER_WORD를 오른쪽으로 6만큼 시프트하기때문에

BitSet의 필드 words의 크기를 조절하고 싶다면 위와 같은 규칙을 잘 숙지하도록 하자.

---

다음은 원소 추가의 set메소드이다.

 

 

파라미터를 오른쪽으로 6만큼 시프트한 결과로 expandTo메소드를 호출하는데...

 

 

필드 words의 크기를 조건분기에 따라 늘려주는 일을 한다.

(max() 함수는 두 인자 값 중 큰 값을 리턴하는 함수)

주목할 부분은

words[wordIndex] |= (1L << bitIndex); // Restores invariants

앞서 손으로 구현한 피자집 토핑추가에 대한 로직이다.

 

 

 

그리고 checkInvariants 메소드.

 

 

 

다음으로는 두번째 인자가 boolean인 set메소드인데 위와 같이 true면 위의 set메소드, false면 clear라는 메소드를 호출하는데 이는 후에 설명할 원소 삭제에 관한 메소드이다.