[Problem Solving Paradigms] Bit - Parallel Algorithms

Bit-Parallel Algorithm | 비트 병렬 알고리즘

 

• 반복문 등을 비트연산자를 이용항 연산으로 변형하여 수행하는 기법
• 비트연산은 다른 연산들에 비해 매우 빠르지만, 사용할 수 있는 범위에 한계가 있으므로 반드시 입력범위 확인이 필요하다
• Complete Search나 DP 등에서 비트연산을 사용하지 않는 경우 간혹 timeout이 발생할 때가 있다.
  •  == 모든 subject에 대한 값을 구해야 하는 경우

 

# 예시

 

1. Hamming Distance

• 길이가 같은 두 bit string a,b가 있을 때, a와 b 사이의 hamming distance( hamming(a,b) )는 a와 b의 symbol이 일치하지 않는 위치의 개수이다. (같은 위치에 있는 symbol끼리 비교)

 

ex) String {00111,01101,11110}이 주어졌을 때

hamming(00111,01101) =2

hamming(00111,11110) =3

hamming(01101,11110) =3

 

#include <iostream>
#include<string>
using namespace std;


int k;

// solution 1

int hamming(string a, string b) {
	int d = 0;
	for (int i = 0; i < k; i++) {
		if (a[i] != b[i]) d++;
	}
	return d;

}

//solution 2
int hamming_2(int a, int b) {
	return __builtin_popcount(a ^ b);
}

 

 

 

2. Counting Subgrids (부분 격자 세기)

 

• n x n grid가 주어지구 그리드의 각 칸은 흰색 혹은 검은 색으로 칠해져 있다고 하자.
• 이때 그리드에서 네 corner가 모두 검은색은 subgrid의 개수를 구하라. (아래 예제의 경우 2개의 subgrid가 있다.)

 

 

# Solution 1

• O(n**2)개의 모든 row pair (a,b)에 대해 O(n)시간을 사용하여 a번째 row와 b번째 row에 공통으로 검은색인 column의 위치를 구한다.
• 이 개수를 count라 하면 top과 bottom이 a와 b번재 row인 subgrid의 수는 총 count(count-1)/2 개가 된다.
• O(n**3) time solution

#include <iostream>
using namespace std;
int main(void) {
	int count = 0;
	for(int i = 0; i < n; i++) {
		if (color[a][i] == 1 && color[b][i] == 1)
			count++;
	 }
}

count의 값이 2개 이상일 경우에 직사각형이 생성됨.

count C 2 작업을 수행하여 count(count-1) /2 의 경우가 생성,

 

 

 

# Solution2

• 각 k번째 row를 길이 n의 bitset으로 저장 : 해당 bit set을 row[k]라고 한다.
• row[k]의 각 i번째 bit가 1이다. grid의 k번째 row, i번재 column은 검은색이ek.

 

• 각 row pair(a,b)에 대해 앞서 정의한 count를 아래와 같이 비트 연산자를 이용하여 O(1)시간에 구할 수 있다.

int cout = (row[a]&row[b]).count();

 

 

시험 끝내줘... 제발... 부탁이야....