Bitwise Property

비스마스크 연산은 O(1) 구현이 많아서 적절히 사용하면 훨씬 빠르다.
특히 집합 연산의 경우 반복문 없이 곧바로 가능한 경우가 많아서 코드가 짧아진다.
같은 데이터를 더 적은 메모리에 표현 가능하다. 따라서 더 많은 데이터를 미리 계산해둘 수 있고, 캐시 효율도 좋아지며, 더 빨라질 수 있다.
XOR 연산은 <> 와 동치. 즉, 두 비트가 다르면 참을 반환한다.
비트마스크 연산자 우선순위는 가장 낮기 때문에, 중첩된 연산 식에 쓰일 때에는 항상 괄호를 쳐주자.
C++에서 1은 부호있는 32비트 상수 로 취급되므로, 부호없는 64비트 1을 쓰고 싶다면 항상 =1ull=의 형태로 쓰자.
32비트 또는 64비트 전체 비트를 쓰고 싶다면 항상 부호없는(unsigned) 정수를 쓰자. 음수를 잘못 쉬프트 하면 1이 채워질 수 있다.

응용

2의 제곱수 판별 (1)

2의 보수 표현에서 다음 등식이 성립한다: -x = ~x + 1

예를 들어 x = 7 인 경우를 살펴보면 다음과 같다.

x = 7;
0 0 0 0 0 1 1 1  // x
1 1 1 1 1 0 0 0  // ~x
1 1 1 1 1 0 0 1  // ~x + 1 == -x

직접 x + (~x + 1) 을 계산해보면 전부 0이 된다는 것을 알 수 있다. 즉, 2의 보수 표현에서 -x = ~x + 1 이다.

이제 이 성질을 가지고 다음과 같이 x 의 가장 오른쪽에 있는 1인 비트 의 위치를 알아낼 수 있다.

x = 7;
0 0 0 0 0 1 1 1  // x
1 1 1 1 1 0 0 1  // -x
0 0 0 0 0 0 0 1  // x & -x

x = 6;
0 0 0 0 0 1 1 0  // x
1 1 1 1 1 0 1 0  // -x
0 0 0 0 0 0 1 0  // x & -x

즉, 두 수를 AND 연산으로 묶으면 가장 오른쪽에 있는 1인 비트 하나만 남기고 다 Unset 된다.

x 가 2의 제곱수인 경우에 어떻게 되는지 보자.

x = 16;
0 0 0 1 0 0 0 0  // x
1 1 1 1 0 0 0 0  // -x
0 0 0 1 0 0 0 0  // x & -x

x 가 2의 제곱수인 경우 (즉 x = 2**x 꼴) 위와 같이 x & -x = x 가 됨을 알 수 있다.

2의 제곱수 판별 (2)

첫 번째 방법이 가장 오른쪽에 있는 1인 비트만 남기는 방법이었다면, 이와 반대로 가장 오른쪽에 있는 1인 비트를 딱 하나만 지워버리는 방법도 있다.

먼저 x 와 x - 1 의 비트 표현을 살펴보자.

x = 7;
0 0 0 0 0 1 1 1  // x
0 0 0 0 0 1 1 0  // x - 1
0 0 0 0 0 1 1 0  // x & (x - 1)

x = 16;
0 0 0 1 0 0 0 0  // x
0 0 0 0 1 1 1 1  // x - 1
0 0 0 0 0 0 0 0  // x & (x - 1)

즉, x 가 2의 제곱수라면 x & (x - 1) = 0 이 됨을 알 수 있다.

4의 제곱수 판별

그러면 문제를 조금 비틀어서, 어떤 수가 4의 제곱수, 즉 \( x = 4^n \) 꼴로 표현되는 수는 어떻게 판별할 수 있을까?

일단 4의 제곱수는 2의 제곱수이므로 위의 방법을 써서 올바른 1비트의 위치를 갖는지 확인할 수 있다.

4의 제곱수의 경우 2의 제곱수와 거의 비슷하지만 한 자리씩 건너 뛰게 된다. 즉 b1, b100, b10000 과 같은 형태를 지니게 된다. 만약 문제의 조건에 따라 값의 범위가 32비트 정수 이내라면, 이 모든 가능한 경우를 하나로 합치면 b010101010101...0101 꼴이 되고 이를 16진수로 좀더 쉽게 표현하면 0xaaaaaaaa 이 된다. 따라서 아래와 같이 판별할 수 있다.

bool isPowerOfFour(int n) {
  if (n <= 0) return false;
  unsigned long long x = n;
  return ((x & (x - 1)) == 0 && (x & 0xaaaaaaaa) == 0);
}

집합 표현하기

N개의 비트를 가지고 집합을 표현할 수 있다. i번째 원소가 집합에 속해있는지 여부는 i번째 비트가 0인지 1인지 여부로 표현한다. 정수는 32비트 또는 64비트 크기 이므로 N이 이 범위에 속할 때에만 가능하다.

구체적인 예시를 위해 N = 20이라고 하자. 즉 0부터 19까지 총 20개의 원소가 가능하다.

다 켠 경우

N개의 원소를 다 선택한 경우를 상수로 미리 선언해두자. 일일이 1을 채워넣은 바이너리 수식을 써줘도 되지만 간단히 다음과 같이 1을 N만큼 쉬프트한 다음 1을 빼줘도 된다. 괄호 치는거 꼭 잊지말자.

const int full = 0b0000'0000'0000'1111'1111'1111'1111'1111; // 20 1s
// or
const int full = (1 << 20) - 1;

원소 추가

picked = picked | (1 << i);

1을 왼쪽으로 i만큼 시프트하면 i번째 비트만 1인 정수가 되고 이 결과를 이때까지 선택한 picked 에 OR로 합치면 항상 이 원소가 추가되게 된다.

원소 포함 여부 확인 (membership)

if (picked & (1 << i)) {
  // i-th element is contained ...
}

역시 i번째 비트만 1인 정수를 이때까지 선택한 picked 와 AND 연산을 하면 i번째 원소의 포함 여부를 알 수 있다.

원소 삭제

삭제가 좀 트리키하다. i번째 원소를 삭제한다는 것은 i번째 원소의 비트를 끄고, 나머지 비트 는 다 살려둬야 한다. i번째 원소는 항상 0으로, 나머지 원소는 항상 1로 만드는 것이다.

picked = picked & ~(1 << i);

i번째 비트만 꺼지고 나머지 비트는 전부 켜진 정수를 picked 와 AND 연산하면 우리가 원하는 것을 달성할 수 있다.

원소 토글

i번째 비트가 켜져있다면 끄고, 꺼져있다면 켜는 연산인 토글 연산이 종종 유용하다. XOR 연산이 정확히 이것을 해준다.

picked = picked ^ (1 << i);

집합 연산

int added = a | b;         // 합집합
int intersection = a & b;  // 교집합
int removed = a & ~b;      // a에서 b를 뺀 차집합
int toggled = a ^ b;       // a와 b 중 한 쪽에만 포함된 집합 (여집합)

집합 크기

집합의 크기 (Cardinality)를 쉽게 구하는 방법은 딱히 없다. 그냥 일일이 비트를 확인해서 켜진 개수를 세야한다.

int cardinality(int a) {
  if (a == 0) return 0;
  return (a % 2) + cardinality(a / 2);
}

모듈러 연산과 나누기 연산은 비싸니까 어떻게 비트로 좀 쪼개면 다음과 같다.

int cardinality(int a) {
  if (a == 0) return 0;
  return (a & 1) + cardinality(a >> 1);
}

더 최적화할 수 있는 방법이 많지만 굉장히 어렵다고 한다.

다행히도 컴파일러가 몇몇 비트 연산과 관련된 내장 함수를 제공한다.

int card = __builtin_popcount(picked);  // gcc/g++
int card = __popcnt(picked);            // Visual C++

최소 원소 찾기 (최하위 비트 찾기)

최하위 비트부터 원소 순서가 매겨진다고 할 때, 처음으로 켜진 최하위 비트만 구하려면 다음과 같이 하면 된다.

int firstPick = picked & -picked;

이건 앞의 2의 제곱수 판별 (1) 방법과 같다. 즉, 가장 오른쪽(최하위) 1만 남기고 나머지는 다 삭제하는 연산과 같다.

최소 원소 지우기 (최하위 비트 지우기)

최하위 1인 비트만 없애는 연산이 종종 필요한데, 이는 위의 2의 제곱수 판별 (2)의 방법과 같다.

picked = picked & (picked - 1);

모든 부분 집합 순회하기

모든 원소가 아니라 부분 집합 을 순회하는 방법이다. 예를 들어 picked 가 {1, 2, 4} 라면 {1}, {2}, {4}, {1, 2}, {1, 4}, {2, 4}, {1, 2, 4} 를 순회하는 방법이다.

for (int subset = picked; subset; subset = ((subset - 1) & picked)) {
  ...
}

subset 은 전체 집합 picked 에서 시작해서 아무것도 선택되지 않은 공집합(즉 0)이 될 때까지 반복한다. subset - 1 을 하면 (1) 켜져 있던 최하위 비트는 꺼지고 (2) 꺼진 최하위 비트의 모든 하위 비트는 켜지게 된다. 예를 들어 001001000 에서 1을 빼면 001000111 이 된다. (subset - 1) & picked 는 이 값과 원래 집합의 교집합 을 구하는 것과 동일한 의미이고, 이는 곧 (subset - 1) 을 통해 켜진 비트들 중 picked 에 속하지 않는 원소들은 모두 제거되는 것과 동일하다. 따라서 이 연산을 반복하면 picked 의 모든 부분 집합을 방문하게 된다.

우선순위 큐

특정한 제약 조건이 있는 경우에 O(1)의 우선순위 큐를 만들 수 있다.

우선순위의 범위가 정해져 있는 경우. (예: 1부터 140 사이의 정수)
우선순위가 같은 원소에 대해서는 순서가 상관없는 경우.

이런 경우에 우선순위를 비트 연산으로 O(1) 만에 구할 수 있다.

좀더 구체적으로 우선순위가 1부터 140 사이의 정수라고 하자. 각 우선순위마다 원소를 담을 큐 140개(같은 우선순위에 대해서는 순서 상관 없음)를 만들고 , 각 큐에 원소가 있는지 여부를 비트마스크로 표현할 수 있다. 140개의 불린 값을 64비트 정수 세 개에 저장하면, 앞서 살펴본 최하위 비트를 찾는 연산을 통해 모든 큐를 뒤질 필요 없이 가장 우선순위가 높은 원소가 어디 있는지 바로 찾을 수 있다.

참고로 이런 방식의 우선순위 큐가 리눅스 커널의 프로세스 관리를 위해 구현되어 사용된 적이 있다.

Last Update: 2023-04-18 08:12:13 PM