Algorithm - Double Dabble

1. 빠르게 2진수에서 10진수로 변환할 수 있는 방법은 없는가?

• 2진수로 표현된 숫자들을 16진수로 변환하는 과정은 굉장히 쉽다.
• 아래 표처럼 2진수를 4자리씩 끊어서 16진수로 변환할 수 있다.

2진수	16진수
0000	0
0001	1
0010	2
0011	3
0100	4
0101	5
0110	6
0111	7
1000	8
1001	9
1010	A
1011	B
1100	C
1101	D
1110	E
1111	F

 

• 하지만, 2진수로 표현된 숫자들을 10진수로 변환하는 과정은 위와 같이 쉽지 않다.
• 10진수는 0 ~ 9까지만 표현이 가능하며, 1010(A) ~ 1111(F) 는 한 자리 숫자로 표현할 수 없기 때문에 2진수에서 16진수로 변환하는 것 처럼 쉽게 4자리씩 끊어서 읽을 수 없다.
  
  ★ ★ ★ ★ ★ ★ ★ ★ ★
• Q) 그럼, 2진수에서 4자리씩 끊어 10진수를 16진수 처럼 바로 끊어서 읽을 수 있는 방법은 없는건가?
• A) 2진수로 표현된 숫자을 10진수 (BCD)로 빠르게 변환시켜 줄 수 있는 알고리즘이 바로 "Double Dabble 알고리즘" 이다. 

 

 

 

 

2. Double Dabble Algorithm

• Double Dabble 알고리즘은 2진수에서 16진수로 빠르게 변환하는 것처럼 2진수에서 빠르게 10진수(BCD)로 변환시켜주는 알고리즘이.
• Double Dabble Algorithm은 다음과 같은 순서를 갖는다.
  - 변환하고자 하는 2진수의 MSB를 하나씩 BCD의 0의 자리 (10^0)로 옮긴다.
  - 옮기고 난 뒤, BCD을 왼쪽으로 1칸씩 Left Shifting한다.
  - 만약, BCD의 일의 자리가 4보다 크다면 +3 (0011)을 더한다.
• 이에 대해서는 아래 예시와 함께 설명하도록 하겠다.

 

 

 

2.1. 10101(2) 를 BCD로 변환

• 10101(2)를 BCD로 변환 해보록 하겠다.
• Double dabble 알고리즘을 이용하면 다음과 같은 과정을 거쳐 BCD로 변환된다.
  

  남은 이진수	BCD의 10의 자리 ( 10^1 )	BCD의 1의 자리 ( 10^0 )
  0101	0000	0001
  101	0000	0010
  01	0000	0101 (5)
  01	0000	0101(5) + 0011(3) = 1000 (8)
  1	0001	0000
  	0010	0001
  최종	2	1

• 10101(2) 를 BCD 코드로 표현하면 21로 표현 할 수 있다.

 

 

 

 

3. 왜 BCD의 일의 자리 값이 4보다 크면 +3을 하는가?

• 이는 10진수는 1010(A) ~ 1111(F)를 한자리 숫자로 표현할 수 없기 때문이다. 
• 2진수로 표현된 10진수에 대해서 생각해보자.
  1001(2) = 9 (10) 이며, 1001(2) + 0001(2)을 더하면 1010(2) = 10 (10)가 되지만, 이를 10진수로 표현할 방법이 없다.
• 따라서 이처럼 2진수를 BCD 표현함에 있어 자리 올림이 발생하면 +6 (0110)을 더해줌으로서 0으로 만들어 준다.
  → 1001 (2) + 0001 (2) = 1010 (2) + 0110 (2) = 0001 0000 (2)

 

 

4. 그럼, 왜 +3을 더하는 건가?

• 자리 올림이 발생하면 해당 자리 숫자를 0으로 초기화하는 동시에 0으로 만들어 주기 위해 +6을 더해 줘야할 것 같지만, +3을 더해 주게 된다.
• 이는 위 Doubble dabble 알고리즘 과정에서 10^0 자리 수가 4보다 작으면 왼쪽으로 Shfiting하기 때문이다.
• 만약, 10^0의 자리가 4 (0100)이라면 왼쪽으로 Shfit하면 4*2 = 8이 되며, 자리 올림이 발생하지 않는다.
  하지만, 10^0의 자리가 5 (0101)이라면 왼쪽으로 Shift으로 인해 5*2 = 10이 되어 자리 올림이 발생한다.
  
  
• 따라서 4를 기준으로 4보다 크면 Left Shifting으로 인해 자리 올림이 발생하며, 자리 올림로 인한 다음 BCD 자리로의 올림 및 0으로 초기화 하기 위해 +6을 해줘야 하지만, 왼쪽으로 Shifting 할 때마 X2 배씩 늘어 나기 때문에 6 / 2 = 3을 더해 주게 되는 것이다.
  
  
• 따라서 이를 정리하면 다음과 같이 정리할 수 있다.

	자리 올림 발생 여부	추가적으로 더해주는 값	범위
0 ~ 4	자리 올림 발생 X		0000 ~ 0100
5 ~ 9	자리 올림 발셍 O	+ 3 (0011)	0101 ~ 1001