비트마스크(Bitmask) : 이진법 이용

이진법을 이용하여 bit연산을 통해 순열조합 과 같은 것을 구할 수 있다.

 

그렇다면 비트마스크를 사용하는 이유는 무엇일까?

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

 

우선, 이진법을 통해, 2진수에서 특정위치의 숫자가 1인지 0인지를 확인하는 방법을 알아보자.

 

이진법으로 특정위치가 1인지 조회하는법 : 1을 비트연산(<<)시켜서 &연산을한다.

 

 

예시 : 집합[1,2,3,4]에 대한 부분집합을 이진수로 표현

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

 

위와 같다.

 

Java의 Integer에서 bitCount(숫자) 로 2진수로 표현했을때 1의 개수를 세는 메소드가 있다.

 

아래는 Integer.bitCount()를 사용하여 집합 중에 2개만 골라서 출력하는것이다.

for (int i = 0; i < 1 << arr.length; i++) { // 1을 arr의 크기 5만큼 왼쪽 쉬프트 : 31
  if (Integer.bitCount(i) == 2) {//00101 처럼 1이 두개만 들어온거에 대하여..
      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번째 원소를 출력한다

 

 

<참고 주소>

https://hongjuzzang.github.io/bitmask/bit_mask/#-%EC%9B%90%EC%86%8C%EA%B0%80-2%EA%B0%9C%EC%9D%B8-%EB%B6%80%EB%B6%84%EC%A7%91%ED%95%A9

[java] 비트 마스크