이론: 비트 마스킹

[fineman999]

비트 마스크란? 우선, 컴퓨터는 내부적으로 모든 자료를 이진수로 표현한다. 이와 같은 특성을 이용해 정수의 이진수 표현을 자료구조로 쓰는 기법을 비트 마스크라 한다.

[fineman999]

정리

우선! 비트 연산자

비트 마스킹은 기본적으로 비트를 다루는 기법이기 때문에 비트 연산자를 알고 있으면 좋다. 따라서 우선 비트 연산자를 정리하고 가겠다!

AND, OR, XOR

AND 연산 (&): 대응하는 두 비트가 모두 1일 때, 1 반환
OR 연산 (|): 대응하는 두 비트가 하나라도 1일 때, 1 반환
XOR 연산 (^): 대응하는 두 비트가 서로 다르면, 1 반환

1010 & 1111 = 1010
1010 | 1111 = 1111
1010 ^ 1111 = 0101

NOT

NOT 연산 (~): 비트의 값을 반전하여 반환

~1010 = 0101

왼쪽, 오른쪽 Shift

왼쪽 Shift (<<): 왼쪽으로 비트를 옮긴다. (A * 2^B) 의미
오른쪽 Shift (>>): 오른쪽으로 비트를 옮긴다. (A / 2^B) 의미

00001010 << 2 = 101000
00001010 >> 2 = 000010

[fineman999]

문제
11723번: 집합
문제를 보면 x의 범위는 1부터 20이다. 즉 0번째는 0이라고 생각하고 길이가 21인 비트를 떠올릴 수 있다.