비트마스크를 이용한 에라토스테네스의 체

소수 구하기 알고리즘으로 유명한 에라토스테네스의 체는 굉장히 빠르게 동작한다. 그렇기 떄문에 수행 범위를 늘릴 때 부담이 되는 것은 수행 시간이 아닌 메모리이다. 체를 구현할 때는 범위 내의 각 정수가 지워졌는지 여부를 저장해야하는데, 이 부분을 원래는 불린 값 배열을 이용해 표현하는 것이 대부분이다. 32비트 정수가 표현할 수 있는 범위 내의 모든 수에 대해 체를 수행한다고 가정하면 불린 값 배열을 사용하기 위해 4기가바이트의 메모리가 필요하다. 짝수를 제외해 2기가바이트로 줄일 수도 있지만, 여전히 적지 않은 메모리 양이다. 

이 때 비트마스크를 사용하면 메모리 사용량을 8분의 1로 다시 줄일 수 있다.

 

MAX_N개의 원소를 갖는 불린 값 배열을 다음과 같은 배열로 대체한다.

 

unsigned char sieve[(MAX_N + 7) / 8]];

 

이 배열은 [MAX_N / 8] 바이트만을 써서 MAX_N개의 원소를 갖는 불린 값 배열을 구현한다. 이 때 k번 원소가 참인지를 알기 위해서는 k/8번째 원소의 k%8번째 비트가 켜져 있는지를 확인하면 된다. 

 

int n;
unsigned char sieve[(MAX_N + 7) / 8];

// k가 소수인지 확인한다
inline bool isPrime(int k){
	return sieve[k >> 3] & (1 << (k & 7));
}

// k가 소수가 아니라고 표시한다
inline void setComposite(int k){
	sieve[k >> 3] &= ~(1 << (k & 7));
}

// 비트마스크를 사용하는 에라토스테네스의 체의 구현
// 이 함수를 수행하고 난 뒤, isPrime()을 이용해 각 수가 소수인지 알 수 있다
void eratosthenes(){
    memset(sieve, 255, sizeof(sieve));
    setComposite(0);
    setComposite(1);
    int sqrtn = int(sqrt(n));
    for(int i=2; i<=sqrtn; ++i){
    	// 이 수가 아직 지워지지 않았다면
        if(isPrime(i))
        	// i의 배수 j들에 대해 isPrime[j] = false로 둔다
            // i*i 미만의 배수는 이미 지워졌으므로 신경 쓰지 않는다
            for(int j=i*i; j<=n; j+=i)
            	setComposite(j);
    }
}

 

여기서 실제로 비트마스크를 사용하는 부분은 isPrime()과 setComposite()이다. 이들이 비트 연산을 이용해 나눗셈과 나머지 연산을 구현하는 것을 보자. 정수를 오른쪽으로 3비트 shift하는 것은 8로 나누는 것과 같고, 7과 AND 연산하는 것은 8로 나눈 나머지를 구하는 것과 같다.