[비트 마스크] 비트 마스크란? - 4문제

★ 비트(bit)

비트는 이진수(binary digit)로, 컴퓨터에서 사용되는 데이터의 최소 단위이다.

0/ 1 두 개의 값만을 가질 수 있으며, 이 두가지로 숫자를 표현하는 방법을 이진법이라고 한다.

 

★ 비트 마스트(BitMask)

비트연산을 사용해서 부분 집합을 표현할 수 있다.

비트마스크는 알고리즘 아닌 bit를 사용한 테크닉이다.

비트의 형태, 정수의 이진수 표현을 활용한 기법이다.

 

★ 다음과 같은 집합의 부분집합을 표현할 때,

               {0, 1, 2, 3, 4}

 

[방법1] 다음과 같이 존재하는 인덱스로 표현할 수 있고

{0, 1, 2, 3, 4} = 1 1 1 1 1

{0, 2} = 0 0 1 0 1

{2, 3, 4} = 1 1 1 0 0

{2, 4} = 1 0 1 0 0

{1} = 0 0 0 1 0

각 요소는 인덱스처럼 표현할 수 있다.

즉, 집합 I번째 요소가 부분집합에 존재한다면 1을 의미하고 그렇지 않으면 0을 의미한다.

 

[방법2] 2진수를 10진수로 표현할 수도 있다.

{0, 1, 2, 3, 4} = 1 1 1 1 1 = 31

{0, 2} = 0 0 1 0 1 = 5

{2 ,3 4} = 1 1 1 0 0 = 28

{2, 4} = 1 0 1 0 0 = 20

 

★ 비트 연산

A	B	~A	A & B	A | B	A ^ B
0	0	1	0	0	0
0	1	1	0	1	1
1	0	0	0	1	1
1	1	0	1	1	0

 

★ shift 연산자

10<<2 : 10을 왼쪽으로 2비트 이동

<<n : n비트씩 왼쪽으로 이동, 왼쪽으로 밀려나간 비트가 사라지고, 오른쪽 빈자리에는 0이 채워진다. 결과는 10 * 2n을 곱한 것과 같다.

 

10 << 2 : 10을 오른쪽으로 1비트 이동

>>n : 오른쪽으로 밀려나간 비트가 사라지고, 왼쪽 빈자리에는 부호 비트가 채워진다. (양수는 0으로 채워지고, 음수는 1로 채워진다. 만약, 이동 연산자의 부호 없는(unsigned) 정수형이면, 0으로 채워진다.) 결과는 10 / 2n 으로 나눈 것과 같다.

 

 

(a + b) / 2 -> (a+b) >>1로 사용할수 있다. 비트 연산을 통해 추가, 검사, 제거, 토글을 할 수 있다

 

{ 2,  4,  5,  7 }   =  1 0 1 1 0 1 0 0   =   180

0이 포함되어 있는지 검사 180 & 20 = 180 & (1<<0) = 0 1이 포함되어 있는지 검사 180 & 21 = 180 & (1<<1) = 0 2가 포함되어 있는지 검사 180 & 22 = 180 & (1<<2) = 4 3가 포함되어 있는지 검사 180 & 23 = 180 & (1<<3) = 0 4가 포함되어 있는지 검사 180 & 24 = 180 & (1<<4) = 16

 

1을 제거하기 180 & ~21 = 180 & ~(1<<1) = 180 2을 제거하기 180 & ~22 = 180 & ~(1<<2) = 176 3을 제거하기 180 & ~23 = 180 & ~(1<<3) = 180 4을 제거하기 180 & ~24 = 180 & ~(1<<4) = 164

 

1 추가하기 180 | 21 = 180 | (1<<1) = 182 2 추가하기 180 | 22 = 180 | (1<<2) = 180 3 추가하기 180 | 23 = 180 | (1<<3) = 188 4 추가하기 180 | 24 = 180 | (1<<4) = 180

 

1을 토글하기 180 ^ 21 = 180 ^ (1<<1) = 182 2을 토글하기 180 ^ 22 = 180 ^ (1<<2) = 176 3을 토글하기 180 ^ 23 = 180 ^ (1<<3) = 188 4을 토글하기 180 ^ 24 = 180 ^ (1<<4) = 164

 

현재 집합이 S일 때 i를 추가 s | (1 << i)   i를 검사 s & ( 1 << i)   i를 제거 s & ~(1 << i)   i를 토글(1을0으로, 0을 1로) s ^ ( 1 << i )   전체 집합 (1 << N) -1   공집합 0

 

[ 비트마스크 예제1]

#include <cstdio>
int main()
{
	unsigned int data = 0x5678;   //0101 0110 0111 1000
	
	unsigned int bit1 = 0xf000;   // 1111 0000 0000 0000
	unsigned int bit2 = 0x0f00;   // 0000 1111 0000 0000
	unsigned int bit3 = 0x00f0;   // 0000 0000 1111 0000
	unsigned int bit4 = 0x000f;   // 0000 0000 0000 1111
	
	//and연산자를 사용하면 특정 비트열을 뽑아 낼 수 있다. 
	printf("결과 1 = %#.4x \n", data & bit1);
	printf("결과 2 = %#.4x \n", data & bit2);
	printf("결과 3 = %#.4x \n", data & bit3);
	printf("결과 4 = %#.4x \n", data & bit4); 
	
	printf("\n"); 
	
	//or 연산자를 사용하면 비트열의 일부를 변경시킬수 있다. 
	printf("결과 5 = %#.4x \n", data |= bit1);
	printf("결과 6 = %#.4x \n", data |= bit2);
	printf("결과 7 = %#.4x \n", data |= bit3);
	printf("결과 8 = %#.4x \n", data |= bit4); 
	return 0;
}

 

[ 비트마스크 예제2]

#include <cstdio>
int main()
{
	//2번째 비트를 1로 변경 
	// A | 1 << 2 
	printf("%#.4x\n", 0x1010 | 0x0100);
	
	//2번째 비트를 0으로 변경
	// A & ~1 << 2
	printf("%#.4x\n", 0x1110 & 0x1011); 
	
	//2번째 비트의 값을 알 수 있는 방법 
	// A & (1<<i) 
	printf("2번째 비트의 값 = %d\n",0x1010 & 0x0100);
	printf("3번째 비트의 값 = %d\n",0x1010 & 0x1000);
	printf("%d\n", 0x1000111010 & (1<<0)); 
}

 

[ 비트마스크 예제3]

#include <cstdio>
int main() 
{
	printf("180 & (1<<0) = %d\n",  180 & (1<<0));
	printf("180 & (1<<1) = %d\n",  180 & (1<<1));
	printf("180 & (1<<2) = %d\n",  180 & (1<<2));
	printf("180 & (1<<3) = %d\n",  180 & (1<<3));
	printf("180 & (1<<4) = %d\n",  180 & (1<<4));
	printf("---------------\n");
	printf("180 | (1<<0) = %d\n",  180 | (1<<0));
	printf("180 | (1<<1) = %d\n",  180 | (1<<1));
	printf("180 | (1<<2) = %d\n",  180 | (1<<2));
	printf("180 | (1<<3) = %d\n",  180 | (1<<3));
	printf("180 | (1<<4) = %d\n",  180 | (1<<4));
	printf("---------------\n");
	printf("180 ^ (1<<0) = %d\n",  180 ^ (1<<0));
	printf("180 ^ (1<<1) = %d\n",  180 ^ (1<<1));
	printf("180 ^ (1<<2) = %d\n",  180 ^ (1<<2));
	printf("180 ^ (1<<3) = %d\n",  180 ^ (1<<3));
	printf("180 ^ (1<<4) = %d\n",  180 ^ (1<<4));
	printf("---------------\n");
	printf("180 & ~(1<<0) = %d\n",  180 & ~(1<<0));
	printf("180 & ~(1<<1) = %d\n",  180 & ~(1<<1));
	printf("180 & ~(1<<2) = %d\n",  180 & ~(1<<2));
	printf("180 & ~(1<<3) = %d\n",  180 & ~(1<<3));
	printf("180 & ~(1<<4) = %d\n",  180 & ~(1<<4));
	return 0;
}

 

[ 비트마스크 예제4]

#include <cstdio>
int main() 
{
    int n;
    scanf("%d", &n);
 
    //전체집합 = (1<< n)-1  공집합은 제외 
    for (int i=1; i<(1<<n) ; i++) 
	{
		printf("%d = ", i);
  		for (int k=0; k<n; k++) 
	  	{
	  	//	printf("%d", i & (1<<k));
	  		if( i & (1<<k) )
	  			printf("1");
	  		else
	  			printf("0");
    	
    	}
    	printf("\n");   
    }
   
    return 0;
}

 

 

[  비트마스크 문제 풀기 ]

11723번: 집합 (acmicpc.net)

11723번: 집합

1182번: 부분수열의 합 (acmicpc.net)

 

1182번: 부분수열의 합

 

12813번: 이진수 연산 (acmicpc.net)

12813번: 이진수 연산

 

2098번: 외판원 순회 (acmicpc.net)

2098번: 외판원 순회

 

1562번: 계단 수 (acmicpc.net)

1562번: 계단 수