Bitwise operation IV

가장 오른쪽의 1인 비트의 위치를 알기 위해서는 간단한 수식을 정의할 수 있습니다. 여기서는 \( \rho (x) \)란 함수를 정의해서 사용하고자 합니다. 이 함수는 x란 숫자가 입력되었을 때, 가장 오른쪽의 1인 비트의 위치를 0부터 시작해서 표시하는 함수입니다. 애석하게도 \( \rho (0) \)에 대해서는 정의를 내릴 수가 없습니다.

 

\[ \rho(2x) = \rho(x) + 1 \]

\[ \rho(2x+1) = 0 \]

\[ \rho(x-y) = \rho(x \oplus y) \]

 

사실 여기서 어떤 힌트를 얻어서 알고리즘을 만드는 것은 아닙니다. 오히려 우리가 얻어야 하는 힌트는 다른 데에 있습니다. 옛날에 제가 어렸을 때, 숫자를 맞추는 마술카드를 본 적이 있습니다. 이 마술카드는 1부터 50까지의 숫자를 생각하면, 마술카드로부터 생각한 숫자를 맞추는 것입니다. 그 마술카드는 총 6장으로 이루어져 있으며, 각각의 마술카드에는 다음과 같은 숫자가 나열되어 있습니다.

 

Card 1	Card 2	Card 3
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49	2 3 6 7 10 11 14 15 18 19 22 23 26 27 30 31 34 35 38 39 42 43 46 47 50	4 5 6 7 12 13 14 15 20 21 22 23 28 29 30 31 36 37 38 39 44 45 46 47
Card 4	Card 5	Card 6
8 9 10 11 12 13 14 15 24 25 26 27 28 29 30 31 40 41 42 43 44 45 46 47	16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 48 49 50	32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

 

이 카드들은 생각한 숫자가 해당 카드에 있다고 한다면, 카드에 있는 첫 번째 숫자를 더하면 됩니다. 예를 들어서 35를 생각했다면, 1번, 2번, 6번에 있으므로 첫 번째 숫자들을 합하면, 1 + 2 + 32 = 35 가 되어서 생각한 숫자가 됩니다. 이번에 설명할 내용은 이것을 이해해야지 됩니다. 저 카드들은 마술카드라는 거창한 이름이 붙어있지만, 규칙을 알면 아주 쉽습니다. 첫 번째 카드는 이진수로 표현했을 때, 최하위 값이 1이 되는 숫자들입니다. 두 번째 카드는 두 번째 하위 값이 1이고요. 다른 카드들도 마찬가지 방식입니다. 그래서 가장 작은 값들을 더하면 생각한 값이 나오게 되죠.

이 원리를 이용하면 우리는 하나의 숫자를 골라낼 수 있습니다. 마지막 오른쪽 비트를 찾아내는 일도 마찬가지입니다. 첫 번째 카드에 있는 숫자를 0인 비트로 표시하고, 두 번째 카드에 있는 숫자를 0인 비트로 표시한다면, 우리는 다음과 같은 수학 식을 얻을 수 있습니다. 이 수학식은 무한한 숫자에 사용할 수 있죠.

 

 

여기서 사용한 수학식은 조금 복잡합니다만, 일단, 첫 번째 식은 홀수번째 비트에 0을 표시했습니다. 마치 마술카드의 첫 번째 카드처럼요. 두 번째 식은 마술카드의 두 번째 카드처럼 2, 3, 6, 7, .. 번째 비트에 0을 표시했죠. 보시면 똑같다는 것을 알게 됩니다. 그런데 뒤에 있는 숫자는 왠지 생소합니다. 앞의 이진수만 기억하시면 되겠지만, 뒤에 있는 -1/3, -1/5, -1/17 이라는 숫자도 한번 생각해보는 것도 나쁘지 않다고 생각됩니다.

 

 

앞의 숫자는 얼뜻 보기에 분수로 표기될 수 없는 수 같지만, 우리는 -1을 정의할 때 무한한 1을 가진 이진수로 정의하였습니다. 그 정의에 의하면 -1을 3으로 나누면 당연히 몫이 정수 형태로 나옵니다. 그리고 그 꼴은 위에 있는 식과 같습니다. 그리고 우리는 여기서 조금 복잡해 보이는 수 \( 2^{2^k} + 1 \)을 사용합니다. 이 숫자는 페르마의 마지막 정리로 유명한 페르마가 만든 페르마 소수입니다. 아쉽게도 현재까지는 5개의 소수만 밝혀져 있지만요. 이 숫자가 이 알고리즘에서 핵심으로 사용된다는 것은 정말 우연인 듯 합니다.

 

\[ \mu_{d,k} = ( 2^{2^d} – 1 ) / ( 2^{2^k} + 1 ) = \mu_k - \mu_k \lt \lt 2^d \]

 

위 식은 d비트로 한정된 숫자 표현일 때 사용하기 위함입니다. d 값은 2의 멱승수여야 합니다. 그러면 d비트로 한정되었을 때 \( \mu_{d,k} \)를 표현해줄 수 있습니다.

 

그러면 가장 오른쪽 비트를 계산하는 프로그램을 작성해보도록 할께요.

 

 

이 프로그램에서 mu[6]은 위에서 설명한 마술카드와 같은 역할을 합니다. 바로 마술카드의 그 숫자들을 비트값 0으로 표현한 것이죠. rho는 가장 오른쪽 1인 값을 가지는 비트의 위치를 저장하기 위해서입니다. x &= -x 는 이전 게시물에서 설명한 것과 같이 가장 오른쪽 1인 값을 가지는 비트를 제외한 모든 비트를 0으로 만드는 것이죠. 이 프로그램은 가장 오른쪽 1인 값을 비트의 위치를 찾기 위해서 오직 6번의 루프를 돌면 됩니다.