Bit Masking (비트 마스킹)

외판원 길찾기 문제에서 비트마스크 개념이 나오는데 그 개념을 몰라서 차라리 비트마스크를 공부해보자 싶었다.

 

왜 길을 찾는데 비트마스크란 개념을 쓰냐면, 어떤 곳에 방문했는지 탐색할때마다 배열을 만드는건 비효율적이니까 int값만 넘기는데 자릿수마다 어떤 마을에 방문했는지 쓸 수 있는것 이다. (1번째 bit가 1이라면 1번 마을을 방문)

 

대신 넘기는 자료형의 자릿수보다 크게는 안된다. (32bit int 에서는 32까지 표현 가능)

 

 - n번째 비트를 1로 만들기

arr |= (1<<index);

index가 0 일때 맨 오른쪽 비트를 가리킨다

 

index 번째 비트를 1로 만들고 나머지는 그대로 유지한다

 

 - n번째 비트를 0으로 만들기

arr &= ~(1<<index);

index 번째 비트를 0으로 만든다

 

index 번째 비트를 0으로 만들고 나머지는 그대로 유지한다

 

 - n번째 비트가 1인지 확인하기

if ((arr & (1<<index)) == 0) {
	printf("0\n");
} else {
	printf("1\n");
}

index 번째 비트만 1로 해서 &연산

 

자리가 같은곳에 1이 있다면 0이 아닌 수가 나옴

 

 - n번째 비트 전환하기

arr ^= (1<<index);

index 번째 비트만 XOR 연산

 

 - 모든 비트를 1로 만들기

arr &= 0;
arr--;

0에서 1을 빼면 모든 비트가 1이된다 (이진수 특성)