Bitwise operation V

가장 오른쪽 비트의 위치를 알아내는 방법은 전에 소개한 방식이 있지만, 가장 빠른 계산을 할 수 있는 방법은 따로 있습니다. 기본적으로 가장 오른쪽 1인 비트만 남겨두고 나머지 비트들을 0으로 만드는 것은 똑같습니다.

 

우리가 연산을 할 때, 123x100을 생각해보면, 이 연산은 123이라는 숫자를 왼쪽으로 두자리 옮기는 효과가 있습니다. 마찬가지로 이진수에서도 이 방식은 그대로 통용됩니다. 예를 들어서 비트 7에만 1인 숫자가 있다면, 이 숫자를 다른 숫자와 곱하기를 하면, 결과는 7비트만큼 왼쪽으로 쉬프트 한 것과 같습니다. 즉 다음이 성립하는 것이죠.

 

\[ x \times ( …0010^r )_2 = x \lt \lt r \]

 

위 식을 이용하면, 우리는 보다 쉽게 r 의 값을 구할 수 있습니다. 아주 특별한 숫자 x만 구한다면요. 그 특별한 숫자는 다음을 만족해야 합니다. 어느 위치에서든 오른쪽으로 6개의 연속된 비트의 값이 서로 다른 숫자를 고릅니다. 이런 숫자들은 아주 많이 존재합니다. 한 숫자를 고른다면, 0x218a392cd3d5dbf 와 같은 숫자입니다. 이진수로 표현한다면 다음과 같습니다.

 

0000001000011000101000111001001011001101001111010101110110111111.00000

 

제가 소수점을 표현한 이유는 소수점 아래의 5개의 비트도 필요해서이죠. 이 숫자는 어느비트를 골라도 연속된 6개의 비트값은 서로 다릅니다.

 

000000 000001 000010 000100 001000 010000 100001 000011 ....

 

이것을 이용해서 테이블을 만들 수 있습니다. 그렇게 해서 테이블을 이용해서 가장 오른쪽 1인 비트의 위치를 찾아내는 프로그램을 작성하면 다음과 같습니다.

 

int getrmb(unsigned long long x)
{
	unsigned long long m = 0x218a392cd3d5dbf;
	char rho[64] = { 0, 1, 2, 7, 3, 13, 8, 19, 4, 25, 14, 28, 9, 34, 20, 40,
		5, 17, 26, 38, 15, 46, 29, 48, 10, 31, 35, 54, 21, 50, 41, 57,
		63, 6, 12, 18, 24, 27, 33, 39, 16, 37, 45, 47, 30, 53, 49, 56,
		62, 11, 23, 32, 36, 44, 52, 55, 61, 22, 43, 51, 60, 42, 59, 58 };
	x &= -x;
	int index = (m*x)>>58;
	return rho[index];
}