2.11 비트 수 세기
비트의 구성이 어떻게 되어 있는지를 파악하는 두 가지 기능을 작성한다.
하나는 BIGINT수에 대해 '1'인 비트가 몇 개 있는지를 세는 함수인 bitCount(음수의 경우는 '0'인 비트 수), 다른 하나는 수를 나타내기 위해 필요한 비트 길이를 나타내는 bitLength.
예를 들어 십진수 17은 이진수로 10001인데, bitCount(17)=2이고 bitLength(17)=5가 된다.
1) bit_count
먼저 bit_count에 대해서 알아보자.
수를 이진수로 표현했을 때, '1'인 비트 갯수는 아래 표에서 보는 바와 같이, 규칙적이지 않다. 실제 비트를 확인하는 수 밖에 없다.
| 십진수 | 이진수 | 1'비트 수 |
| 1 | 1 | 1 |
| 2 | 10 | 1 |
| 3 | 11 | 2 |
| 4 | 100 | 1 |
| 5 | 101 | 2 |
| 6 | 110 | 2 |
| 7 | 111 | 3 |
| 8 | 1000 | 1 |
| 9 | 1001 | 2 |
| 10 | 1010 | 2 |
| 11 | 1011 | 3 |
| 12 | 1100 | 2 |
| 13 | 1101 | 3 |
| 14 | 1110 | 3 |
| 15 | 1111 | 4 |
| 16 | 10000 | 1 |
어떤 수 A가 n개 비트를 가지고 있다면, 비트를 전부 조사하면서 비트가 '1'인 갯수를 센다면, 아래 코드와 같이 n회 만큼의 비교연산을 해야할 것이다.
int bitCount_u32(u32 n){ int i, cnt=0; u32 c =0x80000000 ; //1000 0000 0000 0000 ... for(i=0;i<32;i++){ if((c & n) != 0) cnt++; c = c >> 1; } return cnt; }
n회가 아닌 더 적은 수의 확인을 통해 알아내는 방법은 없을까?
더 적은 횟수의 연산을 통해 빠르게 비트 수를 알아내는 많은 알고리즘이 있다. 몇 개를 소개해 보자.
int bitCount_u32_PeterWegner(u32 n){ u32 c; for(c=0; n; c++) n &= (n-1); return c; }
위 알고리즘은, '1'인 비트 수 만큼 루프를 돈다. 예를 들어 n이 5=1100이면 2번 루프를 돈다. 단순하면서도 훌륭한 알고리즘이다. 특히 '1'인비트가 적을 때는 아주 빠르게 수행할 것이다. 그러나, 주어지는 수가 32비트 난수이면 '1'인 비트 수는 약16개정도 나올 것이고 그렇다면 16회 정도 루프를 돌게 될 것이다. 즉, 전체 비트수의 약 절반정도 반복연산을 할 것이다.
일반적인 혹은 최악의 경우에 대해서도 반복연산 횟수가 더 적고 효율적인 알고리즘이 있다.
int bitCount_u32_HammingWeight(u32 n){ const u32 m1 = 0x55555555; //01 01 01 01... const u32 m2 = 0x33333333; //00 11 00 11 ... const u32 m3 = 0x0f0f0f0f; //00 00 11 11 const u32 h1 = 0x01010101; //00 00 00 01 n = n - ((n >> 1) & m1); n = (n & m2) + ((n >> 2) & m2); return (((n + (n >> 4)) & m3) * h1) >> 24; }
이 알고리즘은 '1'비트의 갯수에 상관없이 균일한 연산횟수를 가진다. 16개 정도의 '1'비트를 가지는 수에 대해서는 앞에 소개한 bitCount_u32_PeterWegner보다 좀 더 빠른 수행속도를 보일 것이다.
이 알고리즘은 흥미롭게도 '1'인 각 비트를 한 쪽으로 몰고가면서 전체 비트수를 알아내는 방법을 사용한다.
n이 (...1101 0110)이면 처음 식인 n - ((n >> 1) & m1)에 의해 홀수번째 비트로 '1'을 몰아 넣는다. 즉, (...10)이었다면 (...01)이 되고, (...11)이었다면 그대로 (...10)이 된다. 이것은 마치 두 비트에 대해서 '1'인 비트가 몇개인지를 십진수로 나타내는 것과 똑같다. 즉, 두 비트에서 1인 하나인 경우는 (...01)과 (...10)인데, 둘 다 (...01)로 '하나'로 표현되고, '1'이 두 개 있는 경우인 (...11)은 (...10)이 되어 2로 표현된다.
두 비트에 대해서 이렇게 처리한 것을 확장해서, 두 번째 식에서는 4비트에 대한 비트수를 카운트하고, 그 다음은 8비트. 이렇게 확장하면서 최종으로 전체 비트수를 알아내는 것이다.
위 두 알고리즘도 충분히 효율적이지만 가장 빠른 것은 미리 비트수에 대한 배열값을 만들어 두고 사용하는 것이다. 32비트이면 2^32승개의 배열을 만들어 두면 될 테인데, 너무 메모리를 많이 차지할 것이기에 2^8승인 256개 값을 가지는 배열을 만들어 놓고 사용하도록 해보자.
0에서부터 255까지의 수에 대한 비트 수 값을 배열로 만들면 다음과 같다.
* 일일이 손으로 계산한 게 아니고, 앞서 작성한 함수를 이용해서 0에서 255까지의 수에 대해 bitcount를 알아냄.
static u8 cnt16[256] = {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};이제 32비트 수이면 위의 8비트일 때의 비트수 배열을 이용해서, 32비트를 4개 부분으로 나누어서 비트수를 알아낸 후, 4개 값을 합치면 되겠다.
int bitCount_u32(u32 n){ return cnt16[n & 0xffu] + cnt16[(n>>8) & 0xffu] + cnt16[(n>>16) & 0xffu] + cnt16[(n>>24) & 0xffu]; }
이렇게 하면 간단하면서도 아주 빨리 비트수를 알아낼 수 있을 것이다. (물론 256바이트의 고정된 메모리가 사용되긴 하지만)
bitCount_INT
BIGINT는 INT형 배열이고, INT는 16비트 혹은 32비트로 define되어 사용된다. 따라서, INT형 비트수를 세는 것은 정의된 INT형이 무엇인가에 따라, 16비트 수 혹은 32비트 수에 대한 비트카운트를 세야한다.
//32bit형에 대한 '1' bit count int bitCount_u32(u32 n){ return cnt16[n & 0xffu] + cnt16[(n>>8) & 0xffu] + cnt16[(n>>16) & 0xffu] + cnt16[(n>>24) & 0xffu]; } //32bit형에 대한 '1' bit count int bitCount_u16(u16 n){ return cnt16[n & 0xff] + cnt16[(n>>8) & 0xff]; } //INT형에 대한 '1'bit count int bitCount_INT(INT n){ if(sizeof(INT) == 4){ return bitCount_u32(n); }else if(sizeof(INT) == 2){ return bitCount_u16((u16)n); }else{ return -1; } }
BIGINT에 대한 bitCount
이제 최종 목적인 BIGINT에 대한 비트 카운트를 생각해 보자.
BIGINT형은 INT형 배열이므로, 전체 배열값에 대해서 위에서 알아본 bitCount_INT함수를 사용하면 되겠다.
그러나, 이 말은 양수의 경우에만 적용되는 얘기다. BIGINT는 음수도 표현가능하게 설계되어 있고, 음수의 경우는 2의 보수를 사용하게 되어 있으므로, '1'인 비트수가 의미 있는 것이 아니고 '0'인 비트수가 의미있게 된다.
따라서, BIGINT에 대한 bitCount함수는, 양수의 경우에는 '1'인 비트 수를, 음수의 경우에는 '0'인 비트수를 세도록 정의한다.
bit_count(7) = bit_count(0111) = 3
bit_count(-7) = bit_count(1001) = 2
그렇다면, 음수의 경우 어떻게 '0'인 비트를 셀까?
쉽게 전체 비트수에서 1인 비트수를 빼면 될 것이다.
이제 구현을 해보자.
/**************************************************************************
양수의 경우는 모든 '1'인 비트 갯수를,
음수의 경우는 '0'인 비트 갯수 리턴
ex)7=0000 0111 -> 3
-7=1111 1001 -> 2
Input: @A = BigInteger 값
Returns:
bit 갯수(양수이면 1비트 갯수, 음수이면 0비트 갯수)
만약 A가 zero이면, 0을 리턴
Comment:
***************************************************************************/
int bit_count(BIGINT A){
INT *a;
int cnt=0;
a = A + SIZE(A);
if(A[0] == 0) return 0;
함수명은 bit_count로 하고, BIGINT형을 인자로 받는다.
변수로는 A를 따라가면서 계산하는 포인터변수 a와, 최종 알아낸 비트갯수를 저장할 cnt를 선언한다.
포인터변수 a는 A의 끝부분을 가르키게 해서, 배열의 끝에서 부터 처음까지 이동시킬 것이다.
a = A+ SIZE(A)
if(A[0] == 0) return 0;
if(isPositive(A) == 1){ //양수 while(a > A){ cnt += bitCount_INT(*a--); } }else{ //음수 //2's 보수를 나타내는 FF 부분을 pass while(a>A){ if(*a != MAX_INT) break; else a--; } while(a>A){ cnt += ((sizeof(INT)*8) - bitCount_INT(*a--)); } } return cnt; }
양수의 경우는 간단하다. 전체 배열값에 대해서 bitCount_INT함수를 이용해서 각각의 '1'인 비트수를 알아낸 후 전체를 더하면 된다.
cnt += bitCount_INT(*a--);
음수의 경우에는 '0'인 비트수를 세야하는데, 이 경우는 2의 보수 표현법에 의해서 앞부분에 채워져 있을 'FF'값들이 있는 부분은 빠르게 건너 띄고, '0'이 들어 있는 배열값에 대해서만 따로 비트 수를 계산하도록 한다.
'0'이 들어 있는 배열값에 대해서는, 전체 비트수에서 '1'인 비트수를 빼는 것으로, '0'인 비트개수를 알아 낸다.
cnt += ((sizeof(INT)*8) - bitCount_INT(*a--));
2)bit_length
두번째는,주어진 수를 표현하기 위한 유효비트길이를 알아내는 bit_length를 알아 보자.
유효비트란 해당 수를 표현하기 위해 최소로 필요로 하는 비트를 얘기한다. 예를들어 십진수 7은 이진수로 (0111) 이고 유효비트길이는 3이 된다.
| 십진수 | 2의거듭제곱 | 이진수 | 유효비트길이 |
| 0 | 2^0 | 0 | 0 |
| 1 | 1 | 1 | |
| 2 | 2^1 | 10 | 2 |
| 3 | 11 | 2 | |
| 4 | 2^2 | 100 | 3 |
| 5 | 101 | 3 | |
| 6 | 110 | 3 | |
| 7 | 111 | 3 | |
| 8 | 2^3 | 1000 | 4 |
| 9 | 1001 | 4 | |
| 10 | 1010 | 4 | |
| 11 | 1011 | 4 | |
| 12 | 1100 | 4 | |
| 13 | 1101 | 4 | |
| 14 | 1110 | 4 | |
| 15 | 1111 | 4 | |
| 16 | 2^4 | 10000 | 5 |
| 17 | 10001 | 5 |
위의 표에서 유추할 수 있듯이, 유효비트길이는 2의 거듭제곱으로 나타내었을 때의 지수값과 관련이 있다. n이라는 십진수가 있을 때 n에 대한 유효비트길이 p = Ceiling(log2(n+1))로 나타낼 수 있다. 따라서, 유효비트길이를 구하려면 해당 수에 대한 로그값을 구하면 된다. 어떻게 구할까?
쉬운 방법이 있다. 주어진 n값을 2의 거듭제곱과 비교해서 어디에 위치해 있는가를 찾는 방법.
예를 들어, 십진수 13은 2^3과 2^4 사이에 있기에, 유효비트길이 p=4
Binary Search와 같이 Tree구조로 찾는다면, 32비트 수에 대해서 많아도 6번 이내에서 유효비트길이를 찾을 수 있다. 16비트 수에 대해서는 최대 5번 이내.
즉, n이 16의 절반인 2^8 = (1 << 8)보다 큰 쪽인지 작은 쪽에 있는지 비교한 후, 큰 쪽이면 다시 8과 16의 중간값인 12에 대한 지수승인 2^12와 비교하는 것을 반복해서 수행.
이 부분을 코드로 나타내면 다음과 같다.
//find bit length for a 16 bit number of w // bit length = ceil(log2(n)) int bitLength_u16(u16 w){ return( (w < 1 << 8 ? (w < 1 << 4 ? (w < 1 << 2 ? (w < 1 << 1 ? (w < 1 << 0 ? 0 : 1) : 2) : (w < 1 << 3 ? 3 : 4)) : (w < 1 << 6 ? (w < 1 << 5 ? 5 : 6) :(w < 1 << 7 ? 7 : 8))) : (w < 1 << 12 ? (w < 1 << 10 ? (w < 1 << 9 ? 9 : 10) : (w < 1 << 11 ? 11 : 12)) : (w < 1 << 14 ? (w < 1 << 13 ? 13 : 14) : (w < 1 << 15 ? 15 : 16)) ) ) ); }
인자로 unsigned 16비트 형을 받는데 주의한다. 만약 부호가 있는 16비트 형식의 인자를 받는다면, (1 << 15)한 값보다 큰 수는 존재하지 않을 것이고, 대신 0보다 작을 때 16을 리턴하는 코드로 바껴야 할 것이다.
조건문 ?를 써서 코드가 간단하긴 한데, 해석이 쉽지 않다.
코드가 좀 길지만 이해하기는 좀 편한 if~else문으로 나타내면 다음과 같다.
int bitLength_u16_if(u16 w){ if(w < 1 << 8){ //0~8 if(w < 1 << 4){ //0~4 if(w < 1 << 2){ //0~2 if(w < 1 << 1){ //0,1 if(w < 1 << 0){ return 0; }else{ return 1; } }else{ //2 return 2; } }else{ //3,4 if(w < 1 << 3){ return 3; }else{ return 4; } } }else{ //5~8 if(w < 1 << 6){ //5,6 if(w < 1 << 5){ return 5; }else{ //10,11 return 6; } }else{ //7,8 if(w < 1 << 7){ return 7; }else{ return 8; } } } }else{ //9~16 if(w < 1 << 12){ //9~12 if(w < 1 << 10){ //9,10 if(w < 1 << 9){ return 9; }else{ return 10; } }else{ //11,12 if(w < 1 << 11){ return 11; }else{ return 12; } } }else{ //13~16 if(w < 1 << 14){ //13,14 if(w < 1 << 13){ return 13; }else{ return 14; } }else{ //15,16 if(w < 1 << 15){ return 15; }else{ return 16; } } } } }
위는 16비트 수에 대한 유효비트길이를 구하는 코드이고, 32비트에 대해서는 다음과 같다.
int bitLength_u32(u32 w){ return( (w < 1 << 16 ? (w < 1 << 8 ? (w < 1 << 4 ? (w < 1 << 2 ? (w < 1 << 1 ? (w < 1 << 0 ? 0 : 1) : 2) : (w < 1 << 3 ? 3 : 4)) : (w < 1 << 6 ? (w < 1 << 5 ? 5 : 6) : (w < 1 << 7 ? 7 : 8))) : (w < 1 << 11 ? (w < 1 << 9 ? 9 : (w < 1 << 10 ? 10 : 11)) : (w < 1 << 13 ? (w < 1 << 12 ? 12 : 13) : (w < 1 << 14 ? 14 : (w < 1 << 15 ? 15 : 16))))) : (w < 1 << 24 ? (w < 1 << 19 ? (w < 1 << 17 ? 17 : (w < 1 << 18 ? 18 : 19)) : (w < 1 << 21 ? (w < 1 << 20 ? 20 : 21) : (w < 1 << 22 ? 22 : (w < 1 << 23 ? 23 : 24)))) : (w < 1 << 28 ? (w < 1 << 26 ? (w < 1 << 25 ? 25 : 26) : (w < 1 << 27 ? 27 : 28)) : (w < 1 << 30 ? (w < 1 << 29 ? 29 : 30) : (w < 1 << 31 ? 31 : 32)))) ) ); }
위 코드를 if~else구문으로 표현하면 다음과 같다.
int bitLength_u32_if(u32 w){ if(w < 1 << 16){ //0~16 if(w < 1 << 8){ //0~8 if(w < 1 << 4){ //0~4 if(w < 1 << 2){ //0~2 if(w < 1 << 1){ //0,1 if(w < 1 << 0){ return 0; }else{ return 1; } }else{ //2 return 2; } }else{ //3,4 if(w < 1 << 3){ return 3; }else{ return 4; } } }else{ //5~8 if(w < 1 << 6){ //5,6 if(w < 1 << 5){ return 5; }else{ return 6; } }else{ //7,8 if(w < 1 << 7){ return 7; }else{ return 8; } } } }else{ //9~16 if(w < 1 << 11){ //9~11 if(w < 1 << 9){ //9 return 9; }else{ //10,11 if(w < 1 << 10){ return 10; }else{ return 11; } } }else{ //12~16 if(w < 1 << 13){ //12,13 if(w < 1 << 12){ return 12; }else{ return 13; } }else{ //14~16 if(w < 1 << 14){ //14 return 14; }else{ //15,16 if(w < 1 << 15){ return 15; }else{ return 16; } } } } } }else{ //17~32 if(w < 1 << 24){ //17~24 if(w < 1 << 19){ //17~19 if(w < 1 << 17){ //17 return 17; }else{ //18,19 if(w < 1 << 18){ return 18; }else{ return 19; } } }else{ //20~24 if(w < 1 << 21){ //20,21 if(w < 1 << 20){ return 20; }else{ return 21; } }else{ //22~24 if(w < 1 << 22){ //22 return 22; }else{ //23,24 if(w < 1 << 23){ return 23; }else{ return 24; } } } } }else{ //25~32 if(w < 1 << 28){ //25~28 if(w < 1 << 26){ //25,26 if(w < 1 << 25){ return 25; }else{ return 26; } }else{ //27, 28 if(w < 1 << 27){ return 27; }else{ return 28; } } }else{ //29~32 if(w < 1 << 30){ //29,30 if(w < 1 << 29){ return 29; }else{ return 30; } }else{ //31,32 if(w < 1 << 31){ return 31; }else{ return 32; } } } } } }
INT형에 대한 bitLength
INT형은 u16일 수도 u32일수도 있기에, 둘 다 지원되도록 하는 bitLength_INT함수를 만든다.
코드를 보면, INT의 size가 4이면 u32용 함수를, 2이면 u16용 함수를 호출하는 것으로, 간단하다.
//INT형에 대한 유효비트길이 int bitLength_INT(INT n){ if(sizeof(INT) == 4){ return bitLength_u32(n); }else if(sizeof(INT) == 2){ return bitLength_u16((u16)n); }else{ return -1; } }
BIGINT용 유효비트길이
이제 최종 목적인 BIGINT용 유효비트길이를 계산하는 함수를 만들어 보자.
BIGINT형에는 음수가 존재하므로, 양수와 음수에 따라 계산을 달리해야한다.
양수의 경우는, 가장 상위 배열값은 bitLength_INT를 이용해서 유효비트길이를 구하고, 그 밑의 값에 대해서는 sizeof(INT) * 8 만큼씩을 더하면 될 것이다.
음수의 경우는, 양수로 바꾸고 1을 뺀 후, 그 값에 대한 bit_length를 구한다.
코드를 보면 다음과 같다.
/************************************************************************** 유효비트길이를 리턴. 양수 n에 대한 유효비트길이 = Ceiling(log2(n)) 음수의 경우는 2의 보수형태를 띄고 있기에, 0에 대한 유효비트길이를 구하는 것인데, 절대값으로 바꿨을 때 해당하는 양수를 n'이라고 할 때, (n'-1)의 유효비트길이와 같다. 십진수 유효비트길이 십진수 유효비트길이 --------------------------------------------- 0 0 -1 0 1 1 -2 1 2 2 -3 2 3 2 -4 2 4 3 -5 4 5 3 -6 3 6 3 -7 3 7 3 -8 3 8 4 -9 4 Input: @A = BigInteger 값 Returns: 유효비트길이 만약 A가 zero이면, 0을 리턴 Comment: ***************************************************************************/ int bit_length(BIGINT A){ BIGINT C; INT *c; int cnt=0; copy_big(C,A); REMOVE_ZERO(C);if(C[0] == 0) return 0; if(isPositive(A) == 1){ //양수 c = C + SIZE(C); cnt = bitLength_INT(*c--); while(c-- > C){ cnt += (sizeof(INT) * 8); } }else{ //음수 positive(C); decrese(C); if(C[0] == 0) return 0; c = C + SIZE(C); cnt = bitLength_INT(*c--); while(c-- > C){ cnt += (sizeof(INT) * 8); } } return cnt; }
테스트 및 프로젝트 파일
011.bit_count_length.zip
'암호화프로그래밍 > (Old)C-BIGINT' 카테고리의 다른 글
| 019. 기수변환 (0) | 2013.09.03 |
|---|---|
| 018. 거듭제곱 (0) | 2013.08.26 |
| 016. 비트연산 (0) | 2013.08.12 |
| 015. 최대공약수(gcd) (0) | 2013.08.09 |
| 014. 나머지(mod) (0) | 2013.08.08 |