bit masking

알고리즘 문제 중에 외판원 길찾기 문제를 풀려고하다가 비트마스크란 개념이 나오는데 그 개념을 몰라서 헷갈리는 와중에 차라리 비트마스크를 공부해보자 싶었다. 왜 길을 찾는데 비트마스크란 개념을 쓰냐면, 어떤 곳에 방문했는지 탐색할때마다 배열을 만드는건 비효율 적이니까 int값만 넘기는데 자릿수마다 어떤 마을에 방문했는지 정도로 쓸 수 있는것 이다. 대신 넘기는 자료형의 자릿수보다 크게는 안된다.

백준 문제중에 기능을 한번 씩 써볼 수 있는 문제가 있어서 소스 링크를 달아둔다 link

백준 문제에 있는 기능으로 소개를 한다

n번째 비트를 1로 만들기

1
arr |= (1<<index);

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

index 번째 비트를 1로 만든다

1 을 index만큼 left shift 시켜서 or 연산

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

1
arr &= ~(1<<index);

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

index위치만 0으로 하고 나머지 1로 해서 and 연산

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

1
2
3
4
5
6
// 연산자 순위 때문에 괄호 순서 중요
if ((arr & (1<<index)) == 0) {
	printf("0\n");
} else {
	printf("1\n");
}

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

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

n번째 비트 전환하기

1
arr ^= (1<<index);

index 번째 비트를 1로 만든다

1 을 index만큼 left shift 시켜서 xor 연산(반전)

모든 비트를 1로 만들기

1
2
arr &= 0;
arr--;

0 과 and를 하면 0이 된다

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

모든 비트를 0으로 만들기

1
arr &= 0;

0 과 and를 하면 0이 된다

비트 마스크 알고리즘

  • 이제 다시 외판원 문제를 공부해보자