[알고리즘 개념] 비트마스크(Bitmask)

 

비트 마스크를 설명하기 앞서, 비트를 알아야한다. 잘 알면 아래부터 보면 됨!

비트(Bit)

 컴퓨터는 이진수를 통해서 모든 자료를 표현한다.

여기서 사용하는 이진수가 데이터의 최소 단위 Bit(binary Disit)이다.

비트는 0 또는 1의 값을 가지며, n개의 비트는 2^0~2^n-1까지 표현 가능하다.

 

1 = 2^0 = 1
10 = 2^1 = 2
100 = 2^2 = 4
111 = 2^2+2^1+2^0 = 7

3자리의 비트는 1~2^n-1 까지 표현가능

비트 연산자 및 용어 정리

• 최상위 비트(MSB): 2^n-1 비트
• 최하위 비트(LSB): 2^0 비트
• 비트가 켜져있다: 1
• 비트가 꺼져있다: 0
• int는 4byte 총 32비트로 되어있다.
  • ( 최상위 비트는 부호비트 1: -, 0:+)
  • int -1 = bit 11111111111111111111111111111111
  • int -2 = bit 11111111111111111111111111111110
  • 비트가 꺼지는걸로 표기

연산자	의미	설명
a & b	AND	정수 a,b 를 비트 1개씩 비교하여 둘다 1이면 결과 1, 아니면 0
a | b	OR	정수 a,b 를 비트 1개씩 비교하여 둘 중 하나가 1이면 1, 아니면 0
a^b	XOR	정수 a,b 를 비트 1개씩 비교하여 두개가 다르면 1, 같으면 0
~a	NOT	정수 a 각 비트가 1이면 0, 0이면 1로 변환
a<<b	정수 a를 왼쪽으로 b 비트만큼 이동(빈자리 0)
a>>b	정수 a를 오른쪽으로 b비트만큼 이동(빈자리 a의 MSB)
a>>>b	정수 a를 오른쪽으로 b비트만큼 이동(빈자리 0)

연산자 실행코드

public class Test {
    public static void main(String[] args) {
        
        int plus = 1;
        int Minus = -1;

        // 1밖에 안보이지만 앞에 다 0으로 채워져 있음
        System.out.println("1: " + Integer.toBinaryString(plus));
        System.out.println("-1: " + Integer.toBinaryString(Minus));

        int a = 4; // 100
        int b = 7; // 111
        
        // 비트형태로 출력
        System.out.println("a bit: " + Integer.toBinaryString(a));
        System.out.println("b bit: " + Integer.toBinaryString(b));

        // 비트 연산
        System.out.println("a&b: " + Integer.toBinaryString(a&b));
        System.out.println("a|b: " + Integer.toBinaryString(a|b));
        System.out.println("a^b: " + Integer.toBinaryString(a^b));
        System.out.println("~a: " + Integer.toBinaryString(~a));

        a = -16;
        // shift 연산
        System.out.println("a bit: " + Integer.toBinaryString(a));
        System.out.println("a<<2: int("+ (a<<2) +") bit(" + Integer.toBinaryString(a<<2) +")");
        System.out.println("a>>2: int("+ (a>>2) +") bit(" + Integer.toBinaryString(a>>2) +")");
        // 빈자리에 0이 들어와서 부호비트가 0이 되었기때문에 양수로 변환
        System.out.println("a>>>2: int("+ (a>>>2) +") bit(" + Integer.toBinaryString(a>>>2) +")");
        
    }
}

결과값

1: 1
-1: 11111111111111111111111111111111
a bit: 100
b bit: 111
a&b: 100
a|b: 111
a^b: 11
~a: 11111111111111111111111111111011
a bit: 11111111111111111111111111110000
a<<2: int(-64) bit(11111111111111111111111111000000)
a>>2: int(-4) bit(11111111111111111111111111111100)
a>>>2: int(1073741820) bit(111111111111111111111111111100)

비트마스크(BitMask)란

이진수(Bit)를 이용하는 기법.

 

비트마스크를 사용하는 이유

1. 빠른 수행시간
2. 작은 메모리 사용량
3. 간결한 코드

bit연산을 사용하기때문에 O(1) 구현되는게 많고, 하나의 정수로 많은 경우의 수를 표현 가능하기에 메모리 사용량이 적어진다. 또한 집합 연산들을 비트연산자로 작성가능하기에 코드도 간결해진다. (bitCount도 시간복잡도 1)

 

비트연산 사용예시(오른쪽부터 idx 기준)

원하는 연산	코드	설명
공집합, 꽉찬 집합	int a = 0; int a = (1<<a)-1;	0 값은 비트가 다 꺼져있다. (1<<a)-1; 는 a의 개수만큼 비트가 켜져있다.
원소 추가	a |= (1<<k);	k번째에 비트 켜기
원소 삭제	a &= ~(1<<k);	k번째 비트 끄기
원소 확인	a & (1<<k);	k번째 비트 반환
원소 포함여부	if(a &(1<<k) == (1<<k))	a 집합에서 k번째 비트가 켜져있는지 확인
원소 토글	a ^= (1<<k);	k번째 비트 변경(1 -> 0, 0 -> 1)
두집합 연산	a | b; a & b; a & -b a ^ b	집합 a와 집합 b를 합집합 집합 a 와 b를 교집합 a-b 차집합 a와 b중 하나에만 켜진 비트들 집합
집합 내 켜진 원소 개수	Integer.bitCount(a);	a집합내에 켜진 비트수를 반환
왼쪽 원소 모두 0	a &= ((1<<k) -1);	k번째 비트 기준 왼쪽 0
오른쪽 원소 모두 0	a &= (-1<<k);	k번째 비트 기준 오른쪽 0
부분집합 돌기	for (int subA= a ; subA>0; subA = ((subA - 1) & a)){ }	a집합에서 나올 수 있는 부분집합 돌기
최소 원소 찾기	int min = a & (-a);	a집합에서의 켜져있는 비트 중 최소 비트 반환
최소 원소 지우기	a &= (a-1);	a집합에서의 켜져있는 비트 중 최소 비트 끄기

예시코드

 

public class Test {
    public static void main(String[] args) {
        
        int full = (1<<5)-1;
        System.out.println("꽉찬 집합: " + Integer.toBinaryString(full));
        int mfull = -1;
        System.out.println("인트(32비트) 꽉 찬 집합: " + Integer.toBinaryString(mfull));
        
        int a = 32;
        a |= (1<<3);
        System.out.println("4번째 원소 추가: " + Integer.toBinaryString(a));
    
        System.out.println("4번째 원소 반환: " + Integer.toBinaryString(a & (1<<3)));

        a &= ~(1<<3);
        System.out.println("4번째 원소 삭제: " + Integer.toBinaryString(a));

        a ^= (1<<3);
        System.out.println("4번째 원소 토글: " + Integer.toBinaryString(a));

        if((a &(1<<3)) == (1<<3)){
            System.out.println("4번째 원소 포함여부 확인 완료");
        }

        int x = 38;
        int y = 33;

        System.out.println("x: " + Integer.toBinaryString(x));
        System.out.println("y: " + Integer.toBinaryString(y));
        
        System.out.println("합집합: " + Integer.toBinaryString(x|y));
        System.out.println("교집합: " + Integer.toBinaryString(x&y));
        System.out.println("차집합: " + Integer.toBinaryString(x&-y));
        System.out.println("둘중에 하나만 포함집합: " + Integer.toBinaryString(x^y));

        System.out.println("x집합 켜진 원소 수: " + Integer.bitCount(x));

        x &= ((1<<3) -1);
        System.out.println("3번째 원소 왼쪽 0: " + Integer.toBinaryString(x));
        x = 38;
        x &= (-1 <<3);
        System.out.println("3번째 원소 오른쪽 0: " + Integer.toBinaryString(x));

        a = 14; // {4,3,2}
        System.out.println("a: " + Integer.toBinaryString(a));
        for (int subA= a ; subA>0; subA = ((subA - 1) & a)){
            System.out.println("a 부분집합: " +Integer.toBinaryString(subA));
         }
    }
}

 

결과

꽉찬 집합: 11111
인트(32비트) 꽉 찬 집합: 11111111111111111111111111111111
4번째 원소 추가: 101000
4번째 원소 반환: 1000
4번째 원소 삭제: 100000
4번째 원소 토글: 101000
4번째 원소 포함여부 확인 완료
x: 100110
y: 100001
합집합: 100111
교집합: 100000
차집합: 110
둘중에 하나만 포함집합: 111
x집합 켜진 원소 수: 3
3번째 원소 왼쪽 0: 110
3번째 원소 오른쪽 0: 100000
a: 1110
a 부분집합: 1110
a 부분집합: 1100
a 부분집합: 1010
a 부분집합: 1000
a 부분집합: 110
a 부분집합: 100
a 부분집합: 10

 

 

 

---

참조

 

https://loosie.tistory.com/238

[알고리즘] 비트(Bit)와 비트마스크(BitMask) 정리 (Java)

https://ckdgus.tistory.com/38

코딩테스트를 위한 자바(java) 비트마스크 - 6