[Java] Java 에서 비트마스킹을! - BitSet

BitSet

Java로 ‘비트마스킹’을 이용해 알고리즘 문제를 해결할 때 비트 관리를 편하게 할 수 없을까 하다가 찾은 라이브러리이다. 패키지는 java.util.BitSet 이다.

BitSet 은 비트들로 이루어진 vector로, boolean 배열처럼 이용할 수 있다. 그리고 대량의 이진 데이터를 효율적으로 다룰 때에 유용하다. 여러 비트를 한 번에 연산할 수 있기 때문에 메모리 사용량이 낮고 속도가 빠르다. 대규모 데이터 집합에서 중복을 확인하는 데에 유용할 것 같다.

BitSet은 기본적으로 long 형의 배열 64 size를 가진다.

생성자는 아래와 같이 인자의 유무에 상관없이 생성할 수 있다. 인자가 없는 형태의 생성자를 사용한다면 default size 64로 생성될 것이다. 그리고 인자를 기입한다면 해당 길이의 비트 벡터가 생성된다.

class Main{
  public static void main(String [] args){
    BitSet bs = new BitSet(); //default size 64
    
    BitSet bs2 = new BitSet(8); //size 8 bit vector
  }
}

비트 조작

• set(int bitIndex) : 주어진 비트 인덱스를 true(1)로 설정한다.
• clear(int bitIndex) : 주어진 비트 인덱스를 false(0)로 설정한다.
• flip(int bitIndex) : 주어진 인덱스를 0→1, 1→0로 치환한다.
• set(int fromIndex, int toIndex) : 주어진 범위의 비트 인덱스를 true(1)로 설정한다.
• clear(int fromIndex, int toIndex) : 주어진 범위의 비트 인덱스를 false(0)로 설정한다.
• flip(int fromIndex, int toIndex) : 주어진 범위의 비트 인덱스를 0→1, 1→0로 치환한다.
• set(int bitIndex, boolean value) : 주어진 비트 인덱스의 bit 값을 value로 설정한다.(true, false)

비트 값 가져오기

• get(int bitIndex) : 주어진 비트 인덱스의 값을 반환한다. (true, false 형태로)
• get(int fromIndex, int toIndex) : 주어진 범위(fromIndex 이상 toIndex 미만)의 비트를 새로운 BitSet 객체로 반환한다.

비트 연산

• and(BitSet set) : 현재 BitSet 객체와 인자의 BitSet 객체 간의 AND 연산을 수행하여 현재 BitSet 객체에 반영한다.
• or(BitSet set) : OR 연산을 수행하여 현재 BitSet 객체에 반영한다.
• xor(BitSet set) : XOR 연산을 수행하여 현재 BitSet 객체에 반영한다.

카디널리티 연산(true(1)값인 비트의 개수)

• cardinality() : 비트의 값이 true(1)인 개수를 반환한다.

이를 통해 Java로 비트마스킹 알고리즘 문제를 풀거나, 대량의 데이터 중복을 확인할 때 유용하게 사용할 수 있다.

출처

• BitSet이란?
• [자료구조] BitSet
• BitSet (Java Platform SE 7)