[진법 변환 - 1] 2진법에서 BCD로

컴퓨터는
0,1
이 두개 밖에 모른다고 합니다.
즉, 모든 숫자를 0,1 두가지로만 표현해야하며
우리는 통상적으로 컴퓨터는 2진법을 사용하여 숫자를 저장한다고 말합니다.

하지만, 사람은 2진법보다는 10진법에 더 익숙합니다.
101010(2) 보다는 42라고 하는게 더 쉽게 받아들여집니다.

즉, 컴퓨터에 저장되있는 숫자를 확인하려면
10진법으로 확인하는게 편합니다.(사람입장에서.. ^^;)
여기서는 그 변환 방법에 대해 탐구하고자 합니다.

double dabble 알고리즘이란것이 있습니다.
이 알고리즘은 2진법에서 BCD로 변환하는 알고리즘입니다.
나누어서 나머지를 나열하는 것에 비해
쉬프트와 덧셈만을 이용하여 변환하기 때문에 좀 더 효율적이라고 말 할 수 있습니다.

아래 주소는 이 알고리즘에 대한 위키피디아글을 번역한 곳이며
참고하시거나, 혹은 위키피디아에서 직접 확인하시기 바랍니다.

Double Dabble(Shift and add 3) Algorithm  


그리고 다음이 알고리즘을 토대로
c언어로 구현한 코드입니다.
이 코드는 위키피디아 글에 같이 있던 코드이며
제가 임의로 약간 수정을 하였습니다.

 

#include 
#include 
#include 
 
/*
   This function takes an array of n unsigned integers,
   each holding a value in the range [0, 65535],
   representing a number in the range [0, 2**(16n)-1].
   arr[0] is the most significant "digit".
   This function returns a new array containing the given
   number as a string of decimal digits.
 
   For the sake of brevity, this example assumes that
   calloc and realloc will never fail.
*/
void double_dabble(int n, const unsigned int *arr, char **result)
{
	int arbits = 16;
    int nbits = arbits * n;         /* length of arr in bits */
    int nscratch = nbits/3;   /* length of scratch in bytes */
    char *scratch = (char*)calloc(1 + nscratch, sizeof(*scratch));
    int i, j, k;
    int smin = nscratch - 1;    /* speed optimization */
 
    for (i=0; i < n; ++i) {
		j = arbits;
        while (j--) {
            /* This bit will be shifted in on the right. */
            int shifted_in = (arr[i] & (1 << j))? 1: 0;
 
            /* Add 3 everywhere that scratch[k] >= 5. */
            for (k=smin; k < nscratch; ++k)
              scratch[k] += (scratch[k] >= 5)? 3: 0;
 
            /* Shift scratch to the left by one position. */
            if (scratch[smin] >= 8)
              smin -= 1;
            for (k=smin; k < nscratch-1; ++k) {
                scratch[k] <<= 1;
                scratch[k] &= 0xF;
                scratch[k] |= (scratch[k+1] >= 8);
            }
 
            /* Shift in the new bit from arr. */
            scratch[nscratch-1] <<= 1;
            scratch[nscratch-1] &= 0xF;
            scratch[nscratch-1] |= shifted_in;
        }
    }
 
    /* Remove leading zeros from the scratch space. */
    for (k=0; k < nscratch-1; ++k)
      if (scratch[k] != 0) break;
    nscratch -= k;
    memmove(scratch, scratch+k, nscratch+1);
 
    /* Convert the scratch space from BCD digits to ASCII. */
    for (k=0; k < nscratch; ++k)
      scratch[k] += '0';
 
    /* Resize and return the resulting string. */
    *result = (char*)realloc(scratch, nscratch+1);
    return;
}
 
/*
   This test driver should print the following decimal values:
   246
   16170604
   1059756703745
*/
int main(void)
{
    unsigned int arr[] = { 246, 48748, 1 };
    char *text = NULL;
    int i;
    for (i=0; i < 3; ++i) {
        double_dabble(i+1, arr, &text);
        printf("%s\n", text);
        free(text);
    }
    return 0;
}

 

이제
이 코드를 계속계속 수정해나가겠습니다.
필요하신 부분에서 코드를 가져가셔서 사용하시면 될것입니다.

물론 차례차례 바꿔나가겠습니다.