[진법 변환 - 1] 2진법에서 BCD로
전 글에서 2진법에서 BCD로 바꾸는 법에 대해 알아봤습니다.
이제 이것을 약간 바꾸어서 2진법에서 10진법으로 바꿔보겠습니다.
우선 double dabble 알고리즘을 수학적으로 접근해보겠습니다.
2진법으로 표현되는 숫자 n비트를 4비트짜리인 BCD 배열에 저장합니다.
각 BCD에는 0부터 9이하의 숫자가 저장되어야 합니다.
따라서, 10부터 15사이의 값은 다음 BCD에 자리올림을 해주어야합니다.
그래서 5이상인 BCD는 쉬프트 하기전에 3을 더해
8이상으로 만들고 이것을 쉬프트하면
16이상이 되는 원리를 사용, 자리올림을 진행하였습니다.
자 그럼
여기서 BCD의 크기만을 바꿔보겠습니다.
4비트에서 8비트(1바이트)로 말입니다.
원리는 똑같습니다. 다만 숫자만 살짝 바뀝니다.
똑같이 2진법으로 표현되는 숫자 n비트를 8비트짜리 배열에 저장해본다고 합시다.
각 배열 원소에는 0부터 9이하의 숫자가 저장되어야 합니다.(10진법이니깐요.)
따라서, 10부터 255사이의 값은 다음 배열 원소에 자리올림을 해주어야합니다.
그래서 5이상인 배열 원소는 쉬프트 하기전에 123을 더해
128이상으로 만들고 이것을 쉬프트하면
256이상이 되는 원리를 사용, 자리올림을 진행하면 됩니다.
그럼 전 글에서 사용했던 코드가 좀 더 깔끔하게 변하게 됩니다.
아래 코드가 2진법에서 10진법으로 바꾸는 코드입니다.
#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 123 everywhere that scratch[k] >= 5. */
for (k=smin; k < nscratch; ++k)
scratch[k] += (scratch[k] >= 5)? 123: 0;
/* Shift scratch to the left by one position. */
if (scratch[smin] & 0x80)
smin -= 1;
for (k=smin; k < nscratch-1; ++k) {
scratch[k] <<= 1;
scratch[k] |= (scratch[k+1] & 0x80)? 1: 0;
}
/* Shift in the new bit from arr. */
scratch[nscratch-1] <<= 1;
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;
}
다음 글에서는 위 함수를 템플릿함수로 임의의 unsigned 정수형 배열로 부터
가능하게 만들 것입니다.
또한, 2진법에서 10진법만으로 바꾸었지만 다음 글에서는
임의의 진법, 2진법에서 n진법으로 바꾸는 방향으로 작성하겠습니다.
Double Dabble.pdf
DoubleDabble.cpp
