[알고리즘 -4] 비트마스킹

이진수

우리가 평소에 사용하는 0~9의 수는 십진법이다

각각의 자리는 0 ~ 9 로 10개의 숫자로 표현된다

 

컴퓨터는 내부적으로 모든 자료를 0과 1로 표현하는 이진법으로 표현한다

10진수 21을 2진수로 표현해보면  10101 으로 표현한다

각각의 자리는 비트라고 하며 Binary Digit의 약어로 이진수와 같은 개념인 것을 알 수 있다

 

 

비트 연산자 

비트끼리 연산을 할 수 있는 연산자가 있다

 

 

비트 연산자 활용법

 

1. idx 번째 비트 끄기

S & = ~ (1 << idx)

 

 

2. idx 번째 비트 XOR 연산 (0은 1로, 1은 0으로)

S ^ = (1 << idx)

 

 

3. 최하위 켜져 있는 비트 찾기

idx = (S & -S)

 

4. 크기가 n인 집합의 모든 비트를 켜기

(1 << n) - 1

 

이러한 비트를 하나의 배열처럼 쓰기 위해서 비트마스킹을 배운다

ex) 1111은 [1,1,1,1]로 0~3번째 요소가 '포함'되어 있다고 표현할 수 있다

크기가 4라면 (1<<4) -1 로 15 (1111) 가 나온다 

 

 

5. idx번째 비트를 켜기

S | = (1 << idx)

 

 

6. idx번째 비트가 켜져있는지 확인하기

if ( S & (1<< idx ))

 

 

비트마스킹

정수의 이진수 표현을 자료구조로 쓰는 기법

boolean 배열의 역할을 하는 "하나의 숫자"를 만들어서 비트연산자를 통해 탐색, 수정 등의 작업을 하는 것을 말한다

장점

1. 수행시간이 빠르다

2. 코드가 간결하다 

3. 메모리 사용이 적다

 

예를 들어 배열 [0,1,0,1] 으로 만들지 않고, 0101 라는 수를 이용해서 비트연산자를 통해 해당요소가 포함되어 있는지, 없는지 알 수 있는 것이다

 

 

비트마스킹을 이용한 모든 경우의 수

 

{사과, 딸기, 포도, 배}의 모든 경우의 수는 각각 요소는 포함하거나 없거나의 2가지 상태값을 가지기 때문에 2^4=16이

import java.util.*;

public class NumberOfCases{
    public static void main(String[] args) {
       String[] a={"사과", "딸기", "포도", "배"};
	   int n=a.length;
	   
	   for(int i=0;i<(1<<n);i++){
		   StringBuilder ret=new StringBuilder();
		   for(int j=0;j<n;j++){
			   if((i&(1<<j))!=0){
				   ret.append(a[j]).append(" ");
			   }
		   }
		   System.out.println(ret);
	   }
    }
}