비트병렬 알고리즘

string따위의 자료구조를 사용하는 것보다 정수표현에서 비트연산이 훨씬 빠르다는게 요지인 듯 하다.

 

<해밍거리>

0,1로 이루어진 길이가 같은 문자열 s, t에 대해서

해밍거리 hamming(s,t) : 두 문자열이 일치하지 않는 위치의 개수라고 하자.

총 n개의 길이가 k인 문자열 중 두 문자열을 골랐을 때 최소 해밍거리를 구해라.

 

(1) 

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

 

(2)

int hamming(int s, int t) {
	return __builtin_popcount(a ^ b);
}

 

(builtin popcount는 gcc내장함수다. bit 1의 수를 세준다. vs에선 __popcnt()사용하면됨)

둘다 시간복잡도가 O(n*n*k)이지만 (2)방법이 20배빠르다.

k가 30일때 (1)은 n의 크기가 5000이 넘어가면 1초 이내에 들어오지 못한다.

(2)는 n의 크기가 25000이라도 1초 이내에 들어온다