비트마스킹은 비트 연산을 통해 비트 자체에 어떤 정보를 저장하는 테크닉입니다. 종종 데이터가 0과 1(true/false)만 존재할 때가 있습니다. true와 false를 가장 편하게 다루는 방법은 bool을 사용해서 처리하는 방법이 있지만 bool은 1바이트의 크기를 갖습니다. 2진수로 표현해 보면 00000000 또는 00000001만 사용하고 나머지 7개의 비트는 의미없이 버리는 값이 됩니다. 비트마스킹은 비트 자체에 데이터를 저장해 변수 하나에 여러 값을 효율적으로 담을 수 있도록 하는 기법입니다. 32비트 int는 32개의 2진 데이터를 담을 수 있고 64비트 int는 64개의 2진 데이터를 담을 수 있습니다. 실제로 C++의 vector<bool>은 내부적으로 bool 배열을 사용하는 대신 비트마스킹을 통해 효율적으로 데이터를 저장하도록 구현되었습니다. 파이썬에서는 숫자 범위가 무한하니 개수를 크게 생각하지 않아도 됩니다.
비트 연산
비트마스킹을 하려면 비트와 친해져야 합니다. 예를 들어 어떤 4비트 정수에 0110이라는 값이 저장되어 있다면 이것을 6으로 보지 말고 1번, 2번 비트가 1이고 0번 3번 인덱스가 0이라고 생각합니다(제일 오른쪽 부터 0번째 입니다). 평소 사용하는 +, - 같은 대수 연산 말고 비트 자체를 사용하는 비트 연산을 사용해서 비트를 직접 조작하게 됩니다. 컴퓨터는 내부적으로 2진수를 사용하니 비트 연산이 컴퓨터에겐 훨씬 빠르고 자연스럽습니다. 그래서 종종 비트 연산으로 대체되는 연산이 있다면 비트 연산으로 쓰는 코드를 볼 수 있습니다.
Bitwise Shift 연산은 비트를 원하는 위치로 옮기는 연산입니다. 예를 들어, 10번째 비트(\( 2^{10} \))에 1을 넣고 싶다면 아래와 같이 할 수 있습니다.
1 << 10Bitwise AND 연산은 비트끼리 AND 연산을 수행한 결과를 얻는 연산입니다. 원하는 자리의 비트만 뽑아낼 수도 있고 원하는 자리의 비트를 0으로 만들어 버릴 수 있습니다.
5 & 7 // 0101 & 0111 = 0101AND 연산을 이용한 트릭으로 어떤 수가 홀수 인지 확인할 수 있습니다. 2진수에서 홀수는 유일하게 1을 가질 수 있는 LSB(0번째 비트)에 의해서 결정되니 1과 AND 연산을 해서 1이 나오면 홀수이고 0이면 짝수입니다. % 연산보다 비트 연산이 훨씬 빠르니 효율적입니다. 현대 컴파일러는 % 2 연산을 알아서 비트 연산으로 최적화 해주기도 합니다.
if (n & 1) {
// 홀수
}Bitwise OR 연산은 비트끼리 OR 연산을 수행합니다. 원하는 자리의 비트를 1로 만들 수 있습니다.
5 & 7 // 0101 | 0111 = 0111Bitwise XOR 연산은 비트끼리 XOR 연산을 수행합니다. XOR은 비트마스킹에서는 주로 사용되지는 않지만 어려운 정수론 문제에서 자주 사용되서 언급해 보았습니다. XOR을 수행하면 원하는 비트를 반전시킬 수 있습니다. 예를 들어, -1(111111..)과 XOR을 수행하면 모든 비트를 반전시킬 수 있습니다.
5 ^ 7 // 0101 ^ 0111 = 0010Bitwise NOT 연산은 모든 비트를 반전시킵니다. 위에서 n & 1 으로 어떤 수가 홀수인지 판단할 수 있다고 했었는데, NOT 연산을 통해 LSB를 반전시키면 짝수인지 판단할 수 있습니다. 즉 ~n & 1 을 통해 어떤 수가 짝수인지 판별할 수 있습니다.
1094번: 막대기
1094번: 막대기 문제입니다. 길이가 64인 막대를 반으로 잘라 잘린 절반을 버려도 \( X \)보다 크다면 절반을 버립니다. 만약 버려서 \( X \)보다 작아지면 버리지 않습니다. 다음은 가장 작은 막대를 반으로 잘라 다시 반복해 총 길이가 \( X \)가 될 때까지 반복합니다. 처음 보면 직접 시뮬레이션해서 구해야 하나 생각할 수 있습니다. 물론 막대의 길이가 64밖에 되지 않아서 충분히 가능합니다. 하지만, 잘 생각해 보면 막대를 반으로 계속 자르니 2의 \( n \)제곱 길이의 막대만 최종적으로 남게 됨을 알 수 있습니다. 즉, 2의 거듭제곱의 합이 \( X \)가 될 때 반복을 종료하게 됩니다. 여기서 남아있는 막대를 비트의 1로 생각하면 \( X \)를 2진수로 바꿨을 때 1의 개수가 정답임을 알 수 있습니다. \( X \)가 커봐야 \( 2^6 \)이므로 7번 반복해서 정답을 찾을 수 있습니다.
int main() {
int n; cin >> n;
int ans = 0;
for (int i = 0; i <= 6; i++)
if (n & (1 << i))
ans++;
cout << ans;
}
비트 연산을 사용할 때는 연산자 우선순위에 주의해야 합니다. Shift 연산자의 우선순위가 생각보다 굉장히 낮기 때문에 괄호로 감싸주어야 합니다. 사실 2진수로 바꿨을 때 1의 개수를 세는 방법은 여러가지 방법이 있습니다. 파이썬에서는 bin 함수를 통해 2진수 문자열로 변환할 수 있고, C++20 에서는 std::popcount(n) 을 통해서 1의 개수를 셀 수 있습니다. 하지만, 백준과 많은 온라인 저지에서는 C++17을 사용하기 때문에 popcount는 사용할 수 없습니다. 대신, GCC에서만 사용할 수 있는 비표준 함수인 __builtin_popcount(n) 를 사용해서 1의 개수를 구할 수 있습니다.
int main() {
int n; cin >> n;
cout << __builtin_popcount(n);
}
번외 : Brian Kernighan 알고리즘
Brian Kernighan 알고리즘은 어떤 수를 2진수로 바꿨을 때 1의 개수를 빠르게 구하는 알고리즘입니다. \( N \)위에서 한 것처럼 하나씩 순회하면서 AND 연산을 하지 않고 1을 바로바로 찾아서 없에는 방식입니다. 코드로 먼저 보면 다음과 같습니다.
int main() {
int n; cin >> n;
int ans = 0;
while (n) {
n &= n - 1;
ans++;
}
cout << ans;
}
\( n \)과 \( n-1 \)을 bitwise AND 하면 가장 뒤의 1이 제거됩니다. 예를 들어 \( n \)이 0100 1000 이었다면, \( n - 1 \)은 0100 0111 이 되어 AND 연산을 수행하면 가장 뒤의 1을 없엘 수 있습니다. 다음 반복에서 0100 0000 과 0011 1111 을 AND 하게 되어 0이 되고 반복이 종료됩니다. 이 알고리즘은 그렇게 자주 쓰이진 않지만 번외로 언급해 보았습니다. 그냥 이런게 있구나 하고 넘어가주세요!