비트마스크

비트마스크란 ?

• 정수형 자료형의 이진수 표현을 이용해 특정 상태나 값을 비트 단위로 관리하는 방식
• 메모리를 아끼고, 빠르게 상태를 체크하거나 조작할 수 있음
• 예: 상태값 관리, 플래그 체크, 권한 부여 등

왜 사용하는가 ?

• 효율적인 메모리 사용 (비트 단위로 여러 상태를 한 변수에 저장 가능)
  • 한 비트당 0과 1 두 값을 가질 수 있으므로, n비트로 2^n개의 상태 관리 가능
• 빠른 연산 속도
  • 비트 연산자는 O(1) 시간 복잡도를 가짐
• 플래그 기반 상태 처리에 적합

비트 연산자 정리

자주 쓰는 패턴

mask는 특정 비트 위치만 1로 만드는 값 !!

• 어떤 비트를 조작할지 지정할 때 사용
• 나머지 위치는 0으로 둬서 영향을 주지 않게 함

패턴 예시

let flag = 00000101;
 
// 2번째 비트 ON
flag |= (1 << 1);  // 00000111
 
// 3번째 비트 OFF
flag &= ~(1 << 2); // 00000111 → 00000011
 
// 1번째 비트 TOGGLE
flag ^= (1 << 0);  // 00000011 → 00000010

예시 문제

백준 1322 X와 K

문제

두 자연수 X와 K가 주어진다. 그러면, 다음 식을 만족하는 K번째로 작은 자연수 Y를 찾아야 한다.

X + Y = X | Y

| 는 비트 연산 OR이다.

입력

첫째 줄에 X와 K가 주어진다. X와 K는 2,000,000,000보다 작거나 같은 자연수이다.

⚠️ k번째로 작은 y를 찾기 위해 k번 찾을때까지 계속 반복문을 돌리면 시간초과가 발생한다.

💡 아이디어

우선 x+y = x|y이 성립하기 위해서는 x와 y를 더할 때 자릿수 올림이 일어나지 않아야 한다.

x에서 비트가 1인 자리는 자릿수 올림이 발생하지 않게 y는 0이어야 한다.
x에서 비트가 0인 자리는 y에서 0 또는 1로 채워야 한다.

우리는

1. x가 0인 자릿수에 숫자를 채우고
2. k번째로 작은 y를 구해야 한다.

-> k를 이진수 형태로 나타낸 값을 x가 0인 비트 자리에 그대로 넣어주면 된다 !

💡 구현

x는 2,000,000,000보다 작거나 같은 자연수이다. 2^64 = 21억~ 이므로 x의 0부터 64번째 비트까지 반복한다.
위에서 살펴본 자주 쓰는 패턴 x & (1LL \<\< i) 을 사용해 x의 특정 비트가 1인지 검사한다. 여기서 1LL은 1의 long long int 버전이다.

y |= (1LL \<\< i)는 y의 i번째 비트 값을 1로 설정하는 패턴이다.

for(int i=0; i<65; i++){
    // x의 i번째 비트가 1 -> continue
    if ((x & (1ll << i))) continue;
 
    // k의 k_idx번째 비트가 1인지 확인
    if (k & (1ll << k_idx))
        y |= (1ll << i);
 
    k_idx++;
  }
 

전체코드

#include <iostream>
using namespace std;
 
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
 
  int x, k;
  cin >> x >> k;
 
  long long int y = 0;
  long long int k_idx = 0;
 
  for(int i=0; i<65; i++){
    // x의 i번째 비트가 1 -> continue
    if ((x & (1ll << i))) continue;
 
    // k의 k_idx번째 비트가 1인지 확인
    if (k & (1ll << k_idx))
        y |= (1ll << i);
 
    k_idx++;
  }
 
  cout << y;
 
  return 0;
}

백준 2830 행성 X3

문제

상근이는 초등학교 졸업 여행으로 외계 행성 X3에 방문했었다. 이 행성에 사는 사람들의 이름은 모두 자연수이다. 행성의 거주민은 모두 서로를 알고 있다. 두 X3인은 그들의 친밀도를 자신의 이름을 이진수로 바꾸어서 계산한다. 두 이름을 이진수로 바꾸고, 자리수가 짧은 쪽을 기준으로 정렬한다. 이때, 두 이진수의 각 자리 아래에 두 자리가 같으면 0을, 다르면 1을 적는다. 이 결과 이진수를 다시 10진수로 바꾸면 그들의 친밀도가 된다.

예를 들어, 10과 19의 친밀도는 25이다.

1 0 0 1 1 = 19
0 1 0 1 0 = 10
--------------
1 1 0 0 1 = 25

행성의 가치는 이 섬에 있는 모든 친밀도의 합이다. 행성 거주민들의 이름이 주어졌을 때, 행성의 가치를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 X3 거주민의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 다음 N개의 줄에는 거주민의 이름이 주어진다. 이름은 1,000,000보다 작거나 같은 자연수이다.

⚠️ 거주민의 모든 쌍을 비교하면 시간초과가 발생한다.

💡 아이디어

두 이진수의 각 자리 아래에 두 자리가 같으면 0을, 다르면 1을 적는다.
→ 비트마스크의 XOR 연산자 ^을 이용하면 된다.

모든 거주민의 i번째 비트를 검사하는 방식으로 반복한다. i번째 비트가 1인 거주민 수를 count라 하면, 0인 거주민 수는 n-count가 된다. 그럼 i번째 비트가 다른 거주민 쌍의 수는 count * (n-count)가 된다.

해당 비트의 가중치는 2^i이고, 이는 1ll \<\< i 와 같다. (한 비트를 왼쪽으로 이동하면 2를 곱하는것과 같은 효과이기 때문에 !)

즉, 비트가 다른 거주민 쌍의 수에 해당 자리의 가중치를 곱해 누적하는 방식이다.

전체코드

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
 
  int n;
  cin >> n;
 
  vector<int> names(n);
  for (int i = 0; i < n; i++) {
    cin >> names[i];
  }
 
  long long int result = 0;
  for (int i = 0; i < 21; i++) {
    // 2^20 = 1,048,576
    long long int count = 0;
 
    for (int j = 0; j < n; j++) {
      // names[j] 의 i번째 비트가 1인지 확인
      if (names[j] & (1 << i))
        count++;
    }
 
    result += count * (n - count) * (1ll << i);
  }
 
  cout << result;
 
  return 0;
}