[java] 비트 마스크

비트 연산 도전기

비트마스크가 이해가 쉽사리 되지않아서 나를위해 적어보는 비트연산부터 시작하는 도전기

🧸 비트연산

먼저 비트 연산에 대해 알아보자

🍯 비트 이동 연산자

연산식	설명
x << y	x의 각 비트를 y만큼 왼쪽으로 이동 오른쪽 빈자리는 0으로 채워진다
x >> y	x의 각 비트를 y만큼 오른쪽으로 이동 왼쪽 빈자리는 x의 최상위 부호비트와 같은 값으로 채워진다 산술 자리이동(Arithmetic shift)
x >>> y	x의 각 비트를 y만큼 오른쪽으로 이동 왼쪽 빈자리는 0으로 채워진다 논리적 자리이동(Logical shift)

• 5 << 2
  

• 14 >> 3
  

🍯 비트 논리 연산자

연산자	논리	설명
&	AND	두 비트 모두 1이면 1
|	OR	두 비트 중 1개만 1이면 1
^	XOR	두 비트가 서로 다르면 1
~	NOT	비트 반전(보수)

• 38 & 23
  
• 38 | 23
  
• 38 ^ 23
  
• ~38
  
  결과 11011001에서 부호비트(제일왼쪽 1)를 제외한 1011001을 2의보수로 계산하면 0100111(39)이 나온다

🍯 비트 연산 연습문제

• x & y
  ~,|만 사용
• x의 i번째 비트 확인
  ~,|, &, +, <<, >>만 사용
• x를 이진수로 표현했을 때 1의 갯수
  ~,|, &, +, <<, >>만 사용
• x가 0이면 1, 아니면 0 리턴
  ~,|, &, +, <<, >>만 사용
• x == y이면 1, 아니면 0 리턴
  ~,|, &, +, <<, >>만 사용
• x <= y 이면 1, 아니면 0 리턴
  ~,|, &, +, <<, >>만 사용

🧸 비트마스크

비트마스크(bitmask) : 비트연산에 사용되는 데이터
다중 비트들을 싱글비트 연산 작업에서 켜고 끄거나 상호반전 시킬 수 있다

비트마스크를 사용하는 이유는 무엇일까

• DP나 순열 등 배열 활용만으로 해결할 수 없는 문제
• 작은 메모리와 빠른 수행시간으로 해결이 가능(원소수가 적을 때만)
• 집합을 배열의 인덱스로 표현할 수 있음

🍯 부분집합

배열 [1, 2, 3, 4]가 있을 때 이 배열의 부분집합을 구하면 다음과 같다
[],[1],[2],[3],[4],[1,2],[1,3] … [1,2,3,4]
이 경우, 비트마스킹을 해서 배열의 각 요소를 인덱스로 표현하여 접근할 수 있다

[1,2,3,4] -> 1111
[1,3,4] -> 1011
[1,2] -> 1100
[4] -> 0001
[] -> 0000

이때 1111을 10진수로 변환하면 15이다
즉, 0 ~ 15로 부분집합을 표현할 수 있고(정수로 표현 가능), 이 때 부분집합의 갯수는 16개이다

조회

이진수 10010에서 i번째 비트가 1인지 혹은 0인지 어떻게 확인할 수 있을까
확인할 숫자를 n이라고 하고 i번째 비트를 확인하고 싶다
n & (1 << i)가 0이라면 i번째 비트는 0이다
반대로 0보다 크다면 i번째 비트는 1이다

• 23 & (1 << 2)
  23의 2번째 비트를 조회한다면 23과 1<<2를 &연산한다
  그 결과는 0보다 크므로, 23에 2번째 비트는 1이라는 것이다
  
• 23 & (1 << 3)
  23의 3번째 비트를 조회한다면 23과 1<<3를 &연산한다
  그 결과는 0이고, 23의 3번째 비트는 0이다
  

변경(삽입)

i번째 비트의 값을 1로 변경하려면??
위에서 23의 3번째 비트는 0이라는 것을 확인했으니 1로 변경해보자
` n | (1 « i)를 이용하면 된다 |`연산자의 경우, 두 비트 중 한 비트라도 1이면 1이 나오기 때문이다

• 23 | (1 << 3)
  23의 3번째 비트를 1로 변경하기 위해 23과 1<<3를 |연산한다
  23에서 1인 비트 부분은 그대로 1이되고, 1를 3번 오른쪽 쉬프트한 1000과 |연산을 하므로
  3번째 자리는 1로 변경된다
  

삭제

i번째 비트를 0으로 변경하려면??
위의 변경부분에서 더 나아가서 31의 3번째 비트를 0으로 바꿔서 다시 23으로 만들어보자
1을 0으로 바꾸는 것이기 때문에 &연산을 사용해야한다

위에서 봤던 (1 « 3)과 ? 부분에 들어가는 비트는 무엇이 다를까
바로 NOT연산을 했다는 점이다
~(1«3)으로 비트를 뒤집어주고 &연산을 하면 된다

` n & ~(1 « i)`으로 i번째 비트를 0으로 변경해 줄 수 있다

🍯 원소가 2개인 부분집합

배열 [1,2,3,4,5]로 부분집합을 만들었을 때 원소가 2개인 부분집합을 어떻게 구할 수 있을까?

• 비트마스크 ❌
  재귀식으로 idx번째 원소를 선택하는 경우, 선택하지 않는경우로 뻗어나가며 선택 수가 2인 경우 출력하는 방법으로 구현했다

private static void subsum(int[] arr, boolean[] chk, int idx, int cnt) {
	if (cnt == 2) {
		for (int i = 0; i < chk.length; i++) {
			if (chk[i])
				System.out.print(arr[i] + " ");
		}
		System.out.println();
		return;
	}
	if (idx == chk.length)
		return;
	
	chk[idx] = true;
	subsum(arr, chk, idx + 1, cnt + 1);
	chk[idx] = false;
	subsum(arr, chk, idx + 1, cnt);
}

• 비트마스크 사용

  for (int i = 0; i < 1 << arr.length; i++) { // 1을 arr의 크기 5만큼 왼쪽 쉬프트 : 31
    if (Integer.bitCount(i) == 2) {
        for (int j = 0; j < arr.length; j++) {
            if ((i & (1 << j)) > 0)
                System.out.print(arr[j] + " ");
        }
        System.out.println();
    }
  }
  

  • Integer.bitCount(n)
    java에서 n을 이진수로 표현했을 때 1의 갯수를 리턴한다
  • i & (1 << j)
    i = 5(이진수: 00101)이고 j = 3 이라고 가정했을 때
    1 « 3 은 01000이다
    00101 & 01000을 하면 00000으로 0이 나온다
    & 연산의 결과가 0라는 것은 i가 j번째 원소를 선택하지 않았다라는 것이다

  j = 2 이라고 가정했을 때
  1 « 2 은 00100이다
  00101 & 00100을 하면 00100으로 4가 나온다
  0보다 크기때문에 값과 상관없이(어짜피 j는 1의 갯수가 1개이므로) i가 j번째 원소를 선택했다는 것이다
  그러므로 arr의 j번째 원소를 출력한다

🧸 풀 수 있는 문제

관련해서 풀만한 문제 몇 개
백준 - 일곱 난쟁이
백준 - 막대기
백준 - 외판원 순회

🧸 참고

마스크(컴퓨팅)
[Java] 비트(Shift) 연산자 사용법 & 예제
[Java] 비트 마스크에 대해서 알아보자