Double Dabble 알고리즘을 찾게 된 배경
0b10000000000000000000000000000000000000000000000000000000000000
0010000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000
혹시 위와 같은 2진수 STRING을 10진수 STRING으로 변환 해본적이 있는가?
해본 적이 있다면 아마 아래와 같은 사이트에서 BIG number Convert를 통해서 해본 적은 있을 것이다.
Mobilefish.com - Big number converter
This service allows you to convert big positive integer numbers into binary, decimal, hexadecimal or base64 encoding schemes. The big number bitsize is also calculated. For example: The following hexadecimal big number converted into a decimal encoding sch
www.mobilefish.com
(위의 2진수를 10진수로 바꾸면 아래의 값이 나오게 된다
= 3369993333393829974516064590543816698980103656907106937594942849024 (10진수))
하지만 프로그래밍시 위와 같은 매우 큰 2진수를 10진수로 변환하는데 어려움이 있다.
즉, 문자인 숫자에서 숫자형인 숫자로 Parsing이 위의 2진수를 잘게 쪼개지 않는다면 진행이 되지 않는다. 왜냐하면 기본적으로 지원하는 숫자형들의 자릿수가 적기 때문이다.
| 숫자 형 | 표현 범위 |
| INT 형 | -2,147,483,648 ~ 2,147,483,647 |
| LONG 형 | -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 |
| DECIMAL 형 | +/-7.9228162514264337593543950335E + 28 |
위에서 언급했듯이, 보통 2진수 string에서 10진수 string 변환이라고 하면 2진수 STRING을 int.parse 혹은 long.parse를 통해서 Parsing을 하면 화면에는 10진수 숫자로 바로 표기가 되기 때문에 바로 STRING으로 변환을 해주면 굉장히 쉽게 바꿀 수 있다.
하지만 위와 같이 모든 기본 자료형의 표시 비트( 32bit, 64bit)를 아득히 뛰어넘는 다면 어떻게 할지는 고민해 본적이 없었다.
예를 들자면, 17,256,789,456,123,123,123,123 (10진수)이라는 숫자를 parse (숫자형으로 변환) 하는 경우에 int형과 long형으로 Parsing이 안되기 때문에 Decimal형으로 Parsing을 해보면 어떨지 고민해 본 적은 있지만, Decimal형의 숫자 범위까지 아득히 뛰어넘는 경우에는 Decimal형도 변환이 불가능하기 때문에 다른 방법을 찾아보게 되었다. 그래서 2진수를 쉽게 10진수로 컨버팅 하는 방법은 무엇이 있을지 찾다 보니 Double Dabble 알고리즘을 알게 되었다.
16진수와 10진수 2진수
들어가기에 앞서 16진수의 2진수 표기법을 보자, 16진수는 2진수로 굉장히 쉽게 표현이 가능하다. 2진수로는 10진수를 표현하기는 굉장히 어렵지만 16진수는 굉장히 쉽다.
| 16진수 | 2진수 |
| 0 | 0000 |
| 1 | 0001 |
| 2 | 0010 |
| 3 | 0011 |
| 4 | 0100 |
| 5 | 0101 |
| 6 | 0110 |
| 7 | 0111 |
| 8 | 1000 |
| 9 | 1001 |
| A (10) | 1010 |
| B (11) | 1011 |
| C (12) | 1100 |
| D (13) | 1101 |
| E (14) | 1110 |
| F (15) | 1111 |
위의 표처럼 4자리의 2진수로 16진수의 숫자들을 모두 표현할 수 있다.
다시말해, 2진수를 4자리로 끊어 읽으면 16진법의 숫자가 되는 것이다. 하지만 10진수는 어떨까? 10진수 숫자는 2진수인 1010(2) 전까지만 10진수의 수로 표현이 가능하다. 즉 'A'부터는 10진수의 숫자에는 없는 기호이다. 그렇기에 4자리로 2진수를 끊어 읽더라도 16진수 처럼 10진수로 바로 끊어 읽을 수 있는 방법은 없을까?라는 질문을 던질 수 있다. 그리고 그에 대한 해답은 Double Dabble 알고리즘이 가지고 있다.
Double Dabble Algorithm
In computer science, the double dabble algorithm is used to convert binary numbers into binary-coded decimal (BCD) notation. It is also known as the shift-and-add-3 algorithm, and can be implemented using a small number of gates in computer hardware, but at the expense of high latency. -wikipedia
더블 데블 알고리즘은 2진수 숫자를 2진수로 표현된 10진수 (BCD)로 변환하는 알고리즘이라고 한다. 즉 이 알고리즘을 사용한다면 2진수를 16진수로 변환하는 것처럼 빠르게 변환이 가능한 BCD 형식으로 바뀌는 알고리즘인 것이다.
Double Dabble 알고리즘은 설명을 읽어보면 알겠지만 알고리즘의 순서는 다음과 같다.
- 변환하고 싶은 2진수 앞자리부터 하나씩 10 ^ 0자리 의 1의 자리로 (BCD로 변환할 자리) 옮긴다.
- 옮기면서 BCD 의 자리수를 한칸씩 왼쪽으로 움직인다.
- 만약 10 ^ 0의 자리가 4보다 크다면 3을 더해준 후 다시 2진수의 숫자를 왼쪽으로 옮겨준다.
2진수를 16진수처럼 4자리씩 끊어 읽는것 처럼 10진수도 2진수의 4자리씩 끊어 읽으려면 위의 알고리즘을 적용해 주면 BCD로 쉽게 변환이 가능하다는 것이다.
10000(2) 변환
만약 10000(2) = 16을 변환하고 싶다면 어떻게 해야 할까?
아래의 예를 확인해 보자.
| 반복 횟수 | 10 ^ 1자리 | 10 ^ 0 자리 | 변환하고자 하는 2진수 |
| 1 | 0000 | 0000 | 1 0000 |
| 2 | 0000 | 0001 | 0000 |
| 3 | 0000 | 0010 | 000 |
| 4 | 0000 | 0100 | 00 |
| 5 | 0000 | 1000 | 0 |
| 5-1 | 1000에 +3을 더해준다 => 1011 | ||
| 6 | 0001 | 0110 | |
| 결과 | 0001 | 0110 |
10의 ^ 1 자리의 값 은 1 (10진수)
10의 ^ 0 자리의 값은 0110 으로 6 (10진수)이다
표의 5-1번을 보자 왜 저기에서 +3을 더해주었을까?
> 4 ? +3 모듈?
만약 16진수의 수를 자리 올림 하려고 본다면 15 (F)인 수에서 1을 더해주면 자리 올림이 된다,
2진수 16진수로도 보자면 1111(2)에서 1을 더해주면 1 0000(2)으로 바뀌게 되어 2진수 자리옮김이 되는 것을 알 수 있다.
하지만 2진수로 표현한 10진수는 문제가 있는데
10진수는 1001(2) = 9 (10진수) 에서 1을 더하면 1010(2) = 10 (10진수) 이 되지만 자리옮김이 되지 않는다.
자리옮김이 되지 않는다면 2진수를 10진수처럼 사용하지 못하는 꼴이다.
그렇다면 어떻게 해야 할까? 여기서 +3을 더하면 문제가 해결된다.
왜 +3인 걸까?
이 이유는 생각해 보면 굉장히 쉽다.
위의 알고리즘을 보자 4자리의 2진수 수가 4보다 작으면 << 왼쪽으로 1칸씩 쉬프팅 (자리 옮김을 한다)
만약 1010(2)이라는 숫자를 BCD로 표현하고자 한다면
| 횟수 | 10 ^ 1 자리 | 10 ^ 0자리 | 변환하고 싶은 수 (1010)(2) |
| 1 | 0000 | 0001 | 010 |
| 2 | 0000 | 0010 | 10 |
1번과 2번의 차이는 무엇일까?
1번은 1 (10진수)
2번은 2 (10진수)로 한번 자리를 옮길 때마다 값이 2배가 된다는 것이다.
그렇다면 3번째는?
| 횟수 | 10 ^ 1 자리 | 10 ^ 0자리 | 변환하고 싶은 수 (1010)(2) |
| 3 | 0000 | 0101 | 0 |
| 3-1 | 0101 +3 = 1000 | ||
| 결과 | 0001 | 0000 |
(3-1번 의 10 ^ 0을 보면 이때 10 ^ 0자리의 수가 4를 초과하였기에 +3을 해주었다.)
한번 자리 옮김을 하였기에 2에서 4로 2배 증가하였으며 거기에 숫자 1이 한칸 왼쪽으로 옮겨갔기에 1을 더해주어 총 5가 되었다.
그렇다면 이제 3을 더하는 이유는 금방 알 수 있다.
만약, 내가 가진 숫자가 4라면 왼쪽으로 쉬프팅을 하면? 4 X 2 = 8 이므로 자리올림이 발생하지 않는다.
하지만, 5라면 5 X 2 = 10으로 자리 올림이 발생해야 한다.
그렇다면 자리 올림이 가능하게 하려면?
앞서 살펴보았듯이 16진수 의 자리 올림을 생각하면 알 수 있다. 우리가 살펴본 0000(2) 네자리 2진수는 16진수라고 치면 16진수는 16 = 1111(2) 에서 자리 올림이 되기 때문에 16진수에 있는 2진수로 표현한 10진수를 자리 올림 해주려면 두 진수의 차이인 6만큼을 보정해주면 10진수 자리 올림 또한 16진수에서 이루어진다는 뜻이다.
그리고 Double Dabble 알고리즘에서 숫자를 왼쪽으로 한 칸씩 옮길 때마다 2배씩 값이 늘어나기 때문에 6 / 2를 해주어 +3을 해주는 것이다.
| 변환 X (+3) | 0 부터 4 | 0000 ~ 0100 |
| 변환 O (+3) | 5 부터 9 | 0101 ~ 1001 |
왼쪽으로 자리 옮김을 해주면서 위의 표처럼 2진수의 범위에 있다면 바로 +3을 더해주면 16진수의 자리 올림을 이용할 수 있다.
| (5 + 3) X 2 | 16 = (16 + 0) |
| (6 + 3) X 2 | 18 = (16 + 2) |
| (7 + 3) X 2 | 20 = (16 + 4) |
위 표처럼 7까지는 +3 뒤에 쉬프트 연산을 해주어도 10 ^ 0의 자리에서 (>4 ? +3) 올림이 일어나지 않으므로 편하게 자리옮김이 가능하다.
하지만 8(10) 부터 9까지는 주의할점이 있는데
| (8 + 3) X 2 | 22 = (16 + 6) |
| (9 + 3) X 2 | 24 = (16 + 8) |
뒷자리 숫자가 6 과 8이기 때문에 자리 올림 뒤에 나머지 수의 > 4 ? +3 연산을 해주어야 할지 말지 고민을 해야 한다. 이때 는 마지막 쉬프팅 반복 횟수라면 > 4 ? +3 연산을 나머지 에도 적용 해주지 않아도 되지만, 쉬프팅 횟수가 마지막이라면 > 4? +3 연산을 해주어야 한다.
이와 같은 절차를 모두 통과 하면 > 4? +3을 계속해주어 2진수 4자리로도 10진수로 읽을 수 있는 표현식인 Binary Coded Decimal (BCD)로 컨버팅이 가능한 것이다.
+ 참고 영상
1010(2) 보다 더 큰 숫자의 변환
그렇다면 1010(2)과 같이 작은 수 말고 좀 더 큰 숫자를 변환해 보자.
내가 변환하고 싶은 수는 0b0 1111 1111(2) 즉 255인 10진수다.
| 횟수 | 10 ^ 2 | 10 ^ 1 | 10 ^ 0 | 변환하고 싶은 2진수 (0b0 1111 1111) |
| 1 | 0000 | 0000 | 0001 | 111 1111 |
| 2 | 0000 | 0000 | 0011 | 11 1111 |
| 3 | 0000 | 0000 | 0111 | 1 1111 |
| 3-1 | 0111 +3 = 1010 | |||
| 4 | 0000 | 0001 | 0101 | 1111 |
| 4-1 | 0101 +3 = 1000 | |||
| 5 | 0000 | 0011 | 0001 | 111 |
| 6 | 0000 | 0110 | 0011 | 11 |
| 6-1 | 0110 +3 = 1001 | |||
| 7 | 0001 | 0010 | 0111 | |
| 7-1 | 0111 +3 = 1010 | 1 | ||
| 8 | 0010 | 0101 (마지막 반복 횟수기 때문에 '>4?+3' 연산 하지 않음) | 0101 (마지막 반복 횟수기 때문에 '>4?+3' 연산 하지 않음 |
위처럼 변환하고 나온 나머지를 보면
0010 0101 0101 = 2 5 5 (10진수) 임을 알 수 있다.
위처럼 변환 시에 주의할 점은 10의 ^ 1, 2, 3 자리, 모든 10의 자리에서 4 >? + 3 연산을 해주어야 한다. 이런 식으로 계산을 한다면 굉장히 쉽게 BCD로 변환이 되는 것을 알 수 있다.
추가 예 - 위키피디아
Double dabble - Wikipedia
In computer science, the double dabble algorithm is used to convert binary numbers into binary-coded decimal (BCD) notation.[1][2] It is also known as the shift-and-add-3 algorithm, and can be implemented using a small number of gates in computer hardware,
en.wikipedia.org
PSEUDO 코드
그렇다면 어떻게 코드로 짜야할까?
내 의사 코드는 2진수 STRING만을 오직 받는 함수로 작성해 보았다.
1. 2진수 0인가? => "0" 리턴
2. 2진수 0이 아니라면 내가 쉬프팅 할 2진수 자릿수만큼 아래의 코드를 반복한다.
2-1) 바꾸고자 하는 2진수 앞자리 하나씩 아무것도 없는 문자에 더해준다
2-2) 만약 마지막 반복 횟수가 아니라면, 더해진 문자를 뒤에서부터 4자리씩 끊어서 모든 4자리의 2진수 숫자가 4보다 커졌는지 아닌지 확인하고 크다면 3을 더해준다
2-3) 4보다 큰 수가 없다면 다시 2-1로 돌아간다.
3. 변환된 2진수 리턴
후기
처음 10진수 변환에 관한 double dabble 알고리즘의 실마리를 찾았을 때 이름을 누가 지었는지는 모르겠지만 굉장히 힙한 사람이 지었을 거라 생각이 들었다. 더블 데블 라임이 아주 찰떡궁합이다.... 마치 Binary 는 호남선 처럼....
만약에 2진수를 10진수로 바꿀 때, 우리가 학교에서 배웠듯이 첫 번째 자리는 *2^0 2번째 자리는 * 2^1 이런 식으로 하나하나씩 곱해서 더하는 쉬운 방법을 쓸 수 있겠지만, 반복하는 횟수가 많아져 시간 효율성이 떨어진다고 생각한다. 그렇다면 이번에는 double dabble 알고리즘을 사용해보는 것은 어떨까? 이 알고리즘을 실행한다면 굉장히 빠르게 2진수에서 10진수 변환이 가능할 것이다.
최근댓글