경우의수를 비트마스크로 표현하는 법

---

(사과, 딸기, 포도) 중 에서 선택 할수 있는 총 경우의 수는 어떻게 될까요?

아래 그림과 같이 선택 할수 있습니다.

선택하는 경우를 1, 선택 안하는 경우를 0 으로 표현 할수 있습니다.

이를 이용해서, 경우의수 문제(조합, Combination, DFS)를 비트 마스크를 이용해서 해결 할수 있을거 같습니다.

 

 

1. 비트 마스크

비트 마스크는 이진수로 표현하여, 비트 연산자(&(AND연산자), |(OR연산자), ^(XOR연산자))를 이용하여 각각의 이진수의 값을 마스킹(가리다) 하여, 원하는 연산을 할수 있는 것 입니다.

 

4(십진수) => {1, 0, 0}(이진수)

2(십진수) => {0, 1, 0}(이진수)

1(십진수) => {0, 0, 1}(이진수)

위와 같이 십진수를 이진수로 표현 할수 있습니다. 이 이진수를 컴퓨터의 비트 입니다.

 

2.   &   (AND연산자)

AND연산자는 두 비트가 모두 1일 때, 1을 반환 합니다.

 

3.   |   (OR연산자)

OR연산자는 두 비트가 모두 1 또는 하나라도 1일때, 1을 반환

 

4.   ^   (XOR연산자)

XOR연산자는 두 비트가 서로 다르면 1을 반환

 

5.    <<    (시프트 연산자)

x<<y (시프트 연산자는)는 x를 y만큼 비트를 이동시킨다는 뜻 입니다.

예를들어, 1<<3은 0001(이진수)을 1000(이진수)으로 만들어 버립니다. 

 

 

6. (사과, 딸기, 포도) 3가지 중에서 선택할수 있는 모든 경우의 수는?

1<<3은 {1,0,0,0}(이진수) 입니다. 그러면 (1<<3) > i 경우는 무엇이 있을까요?

- {1,0,0,0} 보다 작은 경우들

{0, 0, 0}

{1, 1, 1}

{1, 0, 0}

{0, 1, 0}

{0, 0, 1}

{0, 1, 1}

{1, 1, 0}

{1, 0, 1}

= 총 8가지 입니다.

이것을 java 소스 코드로 표현해 보면 다음과 같습니다.

for(int i=0; i<(1<<3); i++) {
    System.out.println(i);
}

출력 결과

물론, 위의 출력 된 값은 십진수 입니다.

 

 

7. (사과, 딸기, 포도) 중에서 2가지만 선택 하는 경우는?

{0, 1, 1}

{1, 1, 0}

{1, 0, 1}

이렇게 3가지가 나옵니다.

java에서는 Integer.bitCount()라는 정적 메소드가 있습니다. 이 메소드는 비트가 1인 개수를 반환해 줍니다. java 소스 코드로 구현해 봅니다.

for(int i=0; i < (1<<3); i++) {
    if(Integer.bitCount(i) == 2) {
        System.out.print(i + " ");
    }
}

출력 결과

물론, 위 출력결과는 십진수 입니다.

3(십진수) => {0, 1, 1}

5(십진수) => {1, 0, 1}

6(십진수) => {1, 1, 0}

 

 

8. 위 출력 결과 (3, 5, 6)을 이진수로 변환하고, 변환된 이진수를 배열의 인덱스로 변환 하려면?

j가 0 ~ 2인경우, (1<<j)는

{0, 0, 1}    (= 포도 선택)   (= 0(십진수) 선택)

{0, 1, 0}    (= 딸기 선택)   (= 1(십진수) 선택)

{1, 0, 0}    (= 사과 선택)    (= 2(십진수) 선택)

을 만듭니다.

여기서, i가 3(십진수) = {0, 1, 1}(이진수) 이라면,

i  &  (1<<j)  는

{0, 1, 1}  &  {0, 1, 0}  =  {0, 1, 0}

{0, 1, 1}  &  {0, 0, 1}  =  {0, 0, 1}

을 뽑아낼수 있습니다.

그러면, 3개 중, 2개를 선택하는 경우의 수를 코드로 나타내 보겠습니다.

for(int i = 0; i < (1<<3); i++) {       //3개 중
    if(Integer.bitCount(i) == 2) {      //2개를 선택하는 경우
        for(int j = 0; j < 3; j++) {    //{1,0,0},{0,1,0},{0,0,1}을 j로 만들어 놓음
            if(((1<<j) & i) > 0) {      //선택된 i라는 경우의수의 위치값을 출력
                System.out.print(j+" ");
            }
        }
        System.out.println();           //다음의 경우의수로 넘어감
    }
}

출력 결과

위와 같이 출력 됨을 알수 있습니다. 이것을 String 배열을 만들어 출력시키면 아래와 같습니다.

String[] fruits = {"사과", "딸기", "포도"};

for(int i = 0; i < (1<<3); i++) {       //3개 중
    if(Integer.bitCount(i) == 2) {      //2개를 선택하는 경우
        for(int j = 0; j < 3; j++) {    //{1,0,0},{0,1,0},{0,0,1}을 j로 만들어 놓음
            if(((1<<j) & i) > 0) {      //선택된 i라는 경우의수의 위치값을 출력
                System.out.print(fruits[j] + " ");
            }
        }
        System.out.println();           //다음의 경우의수로 넘어감
    }
}

출력 결과