Double Dabble(Shift and add 3) Algorithm

Double dabble

---

---

From Wikipedia, the free encyclopedia

컴퓨터 과학에서, doublde dabble 알고리즘은 2진수의 수를 10진법(특히, BCD)로 바꾸는데 사용됩니다. 알고리즘은 다음과 같습니다.

변환하고자 하는 n비트의 2진법의 수가 register에 저장되있다고 합시다. 다음으로 원래의 숫자와 변환된 BCD 모두가 저장될 수 있을만큼 충만한 만큼의 비트를 할당합니다. - "n + 4n/3"비트면 충분할겁니다. 이제 할당된 비트를 BCD크기만큼으로 나누어주며(왼쪽에 배치)하고 변환하고자하는 2진법의 수를 오른쪽에 써줍니다. 예를 들어, 만약 변환하고자 하는 숫자가 8비트라면, 할당된 비트는 다음과 같은 모습일 것입니다.

100S   TENS   ONES           ORIGINAL

0010      0100     0011           11110011 

위의 그림은 243₁₀의 2진수 표현(오른쪽)과 BCD식의 243(왼쪽)을 나타냅니다.

할당된 공간은 0으로 초기화 하며, 변환하고자 하는 숫자를 오른쪽에 배치합니다.

 0000 0000 0000           11110011 

이 알고리즘은 n번의 쉬프트를 합니다. 하지만, 쉬프트 하기 전에 4 초과(5 이상)인 BCD블럭에는 3을 더해주어야합니다. 5에 3을 더해고 쉬프트하면 16이 되기때문입니다.
(- 각 BCD블럭은 0에서 9의 숫자를 표현해야 하는데, 5 이상인 블럭은 쉬프트하면 10이상이 됩니다. 각 블럭의 수는 9이하여야 하므로 5이상인 블럭은 쉬프트 하기 전에 3을 더하여 16이상으로 만들어 줍니다. 16은 2진수로 1000이므로 BCD의 다음 블럭으로 비트가 넘어가게 됩니다. 따라서, 올바른 변환이 가능하게 됩니다.)

double-dabble 알고리즘은 243을 다음과 같은 순서에 의해 BCD로 나타내는 243으로 변환이 가능합니다.

0000 0000 0000 11110011      Initialization 0000 0000 0001 11100110      Shift 0000 0000 0011 11001100      Shift 0000 0000 0111 10011000      Shift 0000 0000 1010 10011000      Add 3 to ONES, since it was 7 0000 0001 0101 00110000      Shift 0000 0001 1000 00110000      Add 3 to ONES, since it was 5 0000 0011 0000 01100000      Shift 0000 0110 0000 11000000      Shift 0000 1001 0000 11000000      Add 3 to TENS, since it was 6 0001 0010 0001 10000000      Shift 0010 0100 0011 00000000      Shift

8번의 쉬프트 후에 알고리즘은 끝이 납니다. 왼쪽의 BCD 블럭들이 BCD로 표현되는 243을 보여줍니다.

또다른 예입니다. 65244₁₀을 변환합니다.

104  103  102   101  100    ORIGINAL BINARY 0000 0000 0000 0000 0000     1111111011011100      Initialization 0000 0000 0000 0000 0001     1111110110111000      Shift left (1st) 0000 0000 0000 0000 0011     1111101101110000      Shift left (2nd) 0000 0000 0000 0000 0111     1111011011100000      Shift left (3rd) 0000 0000 0000 0000 1010     1111011011100000      Add 3 to 100, since it was 7 0000 0000 0000 0001 0101     1110110111000000      Shift left (4th) 0000 0000 0000 0001 1000     1110110111000000      Add 3 to 100, since it was 5 0000 0000 0000 0011 0001     1101101110000000      Shift left (5th) 0000 0000 0000 0110 0011     1011011100000000      Shift left (6th) 0000 0000 0000 1001 0011     1011011100000000      Add 3 to 101, since it was 6 0000 0000 0001 0010 0111     0110111000000000      Shift left (7th) 0000 0000 0001 0010 1010     0110111000000000      Add 3 to 100, since it was 7 0000 0000 0010 0101 0100     1101110000000000      Shift left (8th) 0000 0000 0010 1000 0100     1101110000000000      Add 3 to 101, since it was 5 0000 0000 0101 0000 1001     1011100000000000      Shift left (9th) 0000 0000 1000 0000 1001     1011100000000000      Add 3 to 102, since it was 5 0000 0000 1000 0000 1100     1011100000000000      Add 3 to 100, since it was 9 0000 0001 0000 0001 1001     0111000000000000      Shift left (10th) 0000 0001 0000 0001 1100     0111000000000000      Add 3 to 100, since it was 9 0000 0010 0000 0011 1000     1110000000000000      Shift left (11th) 0000 0010 0000 0011 1011     1110000000000000      Add 3 to 100, since it was 8 0000 0100 0000 0111 0111     1100000000000000      Shift left (12th) 0000 0100 0000 1010 0111     1100000000000000      Add 3 to 101, since it was 7 0000 0100 0000 1010 1010     1100000000000000      Add 3 to 100, since it was 7 0000 1000 0001 0101 0101     1000000000000000      Shift left (13th) 0000 1011 0001 0101 0101     1000000000000000      Add 3 to 103, since it was 8 0000 1011 0001 1000 0101     1000000000000000      Add 3 to 101, since it was 5 0000 1011 0001 1000 1000     1000000000000000      Add 3 to 100, since it was 5 0001 0110 0011 0001 0001     0000000000000000      Shift left (14th) 0001 1001 0011 0001 0001     0000000000000000      Add 3 to 103, since it was 6 0011 0010 0110 0010 0010     0000000000000000      Shift left (15th) 0011 0010 1001 0010 0010     0000000000000000      Add 3 to 102, since it was 6 0110 0101 0010 0100 0100     0000000000000000      Shift left (16th)     6      5     2      4     4            BCD

16번의 쉬프트 후에 알고리즘은 끝나며, 올바르게 변환되었음을 알 수 있습니다.

---

다음 글에서
double dabble의 정의를 이용한
진법 변환에 대해 글을 써보겠습니다.
링크 ㄱㄱ


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