2.13 기수변환
이번 장에서는 BIGINT 수를 여러가지 기수로(진법) 변환하는 알고리즘에 대해서 다룬다.
우리의 일상생활에서는 10진수가 주로 쓰이고 있으나, 컴퓨터는 2진수 체계를 기반으로 움직인다.
2진수는 두 개의 숫자 0과 1로 표현될 수 있으며, 10진수는 0에서부터 9까지의 수로 표현될 수 있다. 따라서, n진수라고 하면 0에서부터 n-1까지의 수로 표현될 수 있겠다.
어떤 정수 u가 있을 때, u를 기수가 B인 수 U=(...U2U1U0)B로 나타내려면 다음과 같이 구할 수 있다.
U0 = u mod B
U1 = ⌊u/B⌋ mod B
U2 = ⌊⌊u/B⌋/B⌋ mod B
...
U... = ⌊...⌊u/B⌋/B⌋.../B⌋ mod B = 0 (0이 될 때가지 계속)
예를 들어 십진수 25을 3진수로 나타내기위한 계산은 다음과 같다.
25 mod 3 = 1 ⌊25/3⌋ = 8
8 mod 3 = 2 ⌊8/3⌋ = 2
2 mod 3 = 2 ⌊2/3⌋ = 0
따라서, (25)10 = (221)3
기수변환 코딩(2진수에서 16진수까지)
위의 기수변환 방법을 이용해서, BIGINT수를 원하는 기수로 표현하는 함수를 만들어 보자.
기수로 표현하는 것이 목적이므로, 출력은 해당 기수로 표현되는 문자열로 하자. 이 때, 9이하는 0에서 9까지의 아라비아숫자로, 10에서 15까지는 알파벳 A에서 F까지로 나타내고, 문자배열의 제일 마지막에는 '\0'을 넣어 string형태가 되도록 하자.
즉, 25에 대해서 3진수로 표현한다면 [0]='2' [1]=2 [2]='1' [3]='\0'이 될 것이다.
static char ch[] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'}; //convert supplied BIGINT to given radix number character. (지원:2진수~16진수) char *convert_digit_all(BIGINT A, u8 radix, int *returnCode){ char c[MAX_BIT_LEN+1] = {0,}; //2진수인경우 최대 BIGINT Q; INT r=0, tmp=0; int i,j;
i f(radix < 2 || radix > 16){ *returnCode = E_WrongFormat;c[0] = '\0';
return &c[0]; }
이론적으로는 어떤 기수로든 변환은 가능하지만, 그것을 어떤 문자로 표현하는가는 문제이다. 16진수까지는 이미 잘 활용되는 0~9, A~F까지를 사용하면 되지만, 16진수 이상에 대해서는 난감하다.(물론 특정 문자로 약속한다면 불가능한 것은 아니지만.)
여기서는 16진수 이하까지의 기수만을 지원하도록 하고, 해당 표현문자에 대해 미리 char형 배열로 선언해 둔다.
함수의 형태는, 요청된 radix를 기수로하는 문자열을 구해서 리턴하도록하고, returnCode에 에러코드를 표출하게 한다.
구하는 문자열은 char형 배열변수 c에 담아지게 되는데, c의 길이는 요구되는 기수가 2일 때의 길이, 즉 최대길이가 되는 것을 가정하여 배열크기를 잡는다.
만약 radix가 2에서 16까지의 수가 아니면 에러코드에 WrongFormat을 넣고, 빈 문자열을 만들어서 리턴한다.
copy_big(Q,A); i=0; while(1){ mod_i(Q,(INT)radix,&r); c[i++] = ch[r]; divide_i(Q,radix,Q,&tmp); if(Q[0] <= 0) break; } c[i] = '\0'; //end of string
BIGINT인 A값과 같은 Q를 생성한다. 기수인 radix로 나눈값이 다시 Q가 되면서 끝내 0이될 때까지 반복 계산하기 위해서다.
기수변환 방법에서 설명한 바와 같이, Q mod radix한 값이 요구된 기수로 변환된 값이다. 이 값을 문자 배열 c에 담을 때는, 1에서 F까지의 수를 나타내는 문자배열 ch를 이용해서 해당값에 대한 문자를 저장한다.
이 과정은 Q가 0이될 때까지 반복된다.
만약 A의 값이 십진수로 23이고, 이것을 3진수로 바꾸려는 것이라면, 이 코드까지 실행되었을 때 문자열c에는 "122"가 들어가 있게 된다.
이것을 순서를 바꿔서 "221"이 되게 해줘야 한다.
//little endian형태로 변환 j=0; i--; while(i > j){ //exchange: j ^= i, i ^= j, j ^= i c[j] ^= c[i]; c[i] ^= c[j]; c[j] ^= c[i]; j++; i--; } *returnCode = OK; return &c[0]; }
위 while구문은 문자배열 c의 순서를 바꾸는 것으로, 만일 배열c의 크기가 n이라면 다음과 같이 된다.
c[0] = tmp
c[0] = c[n-1]
c[n-1] = tmp
c[1] = tmp
c[1] = c[n-2]
c[n-2] = c[1]
...
2진수와 16진수로의 변환
위에서 설명한 방법 및 코드는 모든 기수로의 변환을 할 수 있는 방법이긴한데, mod와 divide연산이 반복해서 사용되므로 큰 수에 대한 변환일 때 비효율적이다.
2진수, 4진수, 8진수, 16진수 등 2의 거듭제곱으로 나타낼 수 있는 기수의 경우에는, shift연산을 통해서 보다 효율적으로 변환이 가능하다.
만약 십진수 4386(=0x1122)을 16진수로 바꾸고자 한다면 다음과 같이 하면 된다.
U3 = (0x1122 >> 12) & 0x0f = 1
U2 = (0x1122 >> 8) & 0x0f = 1
U1 = (0x1122 >> 4) & 0x0f = 2
U0 = 0x1122 & 0x0f = 2
2진수로의 변환은 다음과 같다.
U15 = (0x1122 >> 15) & 0x01 = 0
U14 = (0x1122 >> 14) & 0x01 = 0
U13 = (0x1122 >> 13) & 0x01 = 0
U12 = (0x1122 >> 12) & 0x01 = 1
U11 = (0x1122 >> 11) & 0x01 = 0
...
U1 = (0x1122 >> 1) & 0x01 = 1
U0 = 0x1122 & 0x01 = 0
주로 사용되는 진법은 10진수, 16진수, 2진수 이므로, 이 세가지 기수에 대해서만 변환하는 전용 함수를 만들어 보자.
10진수의 경우에는 mod, divide를 이용해서 변환하고, 16진수와 2진수의 경우는 shift연산을 하도록 하면 되겠다.
코드는 아래와 같다.
/************************************************************************** BIGINT 값을 주어진 진수로 바꿈 변환가능한 진수는 2진수, 10진수, 16진수 Input: @A = 변환하려는 BIGINT형 값 @radix = 진수. 허용: 2,10,16 Output: @returnCode - OK: no error Returns: 요구되는 진수로 변환된 문자열. 배열값이 작은쪽이 큰 값. 즉, 0번째에 가장 큰 자릿수 위치하게 표현 - 2진수: 0,1 사용 - 10진수:0~9 사용 - 16진수: 0~9, A~B사용 Comment: ***************************************************************************/ char *convert_digit(BIGINT A, u8 radix, int *returnCode){ char c[MAX_BIT_LEN+1] = {0,}; //2진수인경우 최대 BIGINT Q; INT r=0, tmp=0; INT *a; int i,j; //Case1. (2진수, 10진수, 16진수)만 지원 --> error if((radix != 2) && (radix != 10) && (radix != 16)) { *returnCode = E_WrongFormat; c[0] = '\0'; return &c[0]; } //Case2. A==0 --> c=0 if(A[0] == 0){ *returnCode = OK; c[0] = '\0'; return &c[0]; } // Case3. 10진수 if(radix == 10){ copy_big(Q,A); i=0; while(1){ mod_i(Q,(INT)radix,&r); c[i++] = ch[r]; divide_i(Q,radix,Q,&tmp); if(Q[0] <= 0) break; } c[i] = '\0'; //end of string //little endian형태로 변환 j=0; i--; while(i > j){ //exchange: j ^= i, i ^= j, j ^= i c[j] ^= c[i]; c[i] ^= c[j]; c[j] ^= c[i]; j++; i--; } *returnCode = OK; return &c[0]; } // Case 4. 16진수 if(radix == 16){ a = A + SIZE(A); i=0; for(j=(sizeof(INT)*2-1);j>=0;j--){ r = (*a >> (4 * j) ) & 0x0f; //숫자 앞에 있을 수 있는 0 없앰 if( (i == 0) && (r == 0)){ continue; }else{ c[i++] = ch[r]; } } a--; while(a > A){ for(j=(sizeof(INT)*2-1);j>=0;j--){ r = (*a >> (4 * j) ) & 0x0f; c[i++] = ch[r]; } a--; } c[i] = '\0'; *returnCode = OK; return &c[0]; } // Case 5. 2진수 if(radix == 2){ a = A + SIZE(A); i=0; for(j=(sizeof(INT)*8-1);j>=0;j--){ r = (*a >> j ) & 0x01; //숫자 앞에 있을 수 있는 0 없앰 if( (i == 0) && (r == 0)){ continue; }else{ c[i++] = ch[r]; } } a--; while(a > A){ for(j=(sizeof(INT)*8-1);j>=0;j--){ r = (*a >> j ) & 0x01; c[i++] = ch[r]; } a--; } c[i] = '\0'; *returnCode = OK; return &c[0]; } return &c[0]; }
프로젝트 파일
012.digit_conversion.zip'암호화프로그래밍 > (Old)C-BIGINT' 카테고리의 다른 글
| 021. 소수(Prime Number) (0) | 2013.09.12 |
|---|---|
| 020. 난수(Random Number) (0) | 2013.09.11 |
| 018. 거듭제곱 (0) | 2013.08.26 |
| 017. 비트 수 세기 (0) | 2013.08.22 |
| 016. 비트연산 (0) | 2013.08.12 |