알고리즘 - 비트 마스킹

✔ 비트 마스킹

• 지금까지 boolean[] 을 통해 정보 저장
• 정수와 비트 연산자를 사용해 해당 원소에 대한 비트 정보 표현

// 비트 마스킹 활용 순열.
T input[]; 		// 데이터 배열
int numbers[];	// 순열 저장 배열

void perm(int cnt, int N, flag){
	if (cnt == N){
    	// 순열 완료
    }
    else{
    	for (int i = 0; i < N; i++){
        	// 비트 AND 연산을 통해 i번째 데이터의 사용 확인.
        	if ((flag & (1 << i)) != 0) continue;
            numbers[cnt]  = input[i]
            // 비트 OR 연산을 통해 i번째 데이터의 상태 변경.
            perm(cnt+1, flag | 1 <<i);
        }
    }
}

◾비트 연산자

연산자	연산자의 기능
&	비트 단위 AND 연산.
|	비트 단위 OR 연산.
^	비트 단위 XOR 연산.
~	단항 연산자. 비트 반전.
<<	피연산자의 비트 열을 왼쪽으로 이동.
>>	피연산자의 비트 열을 오른쪽으로 이동.

◾비트 마스킹 동작

• 비트열의 값이 중요한 게 아니라, 해당 자리(index)에 해당하는 값의 사용을 검사하는 용도
  • int → boolean[32]
  • long → boolean[64]