BCD와 일반적인 2진표현

BCD는 이진화십진코드(2진수 4비트를 묶어서 10진수 한자리를 나타내는 코드)의 약자.
따라서 BCD는 십진수로 표현하기가 쉽다. 하지만 일반적인 2진수는 10진수로 나타내는게 쉽지가 않다.
그래서 사용하는 알고리즘이 시프트 더하기 3 알고리즘, (double dabble)알고리즘이다.

이 알고리즘은 간단하게 설명하면 다음과 같다.

• 일반 2진수 코드를 왼쪽으로 1비트씩 시프트한다.
• 4비트씩 묶어서 5 이상이 되는 자리에는 3을 더해준다.
• 모든 비트가 다 왼쪽으로 시프트 될때까지 위 과정을 반복한다.

log2=약 0.3010 이므로 십진수 한자리를 표현하려면 약 3.33비트가 필요하다.
예를 들어 이진수 11001100을 BCD코드로 변환해보자. 대략 BCD코드가 3자리 필요할거다.

0000 0000 0000 11001100 (왼쪽으로 1비트 시프트)

0000 0000 0001 10011000 (왼쪽으로 1비트 시프트)

0000 0000 0011 00110000 (왼쪽으로 1비트 시프트)

0000 0000 0110 01100000 (BCD코드 첫째자리가 6으로 5이상이므로 3을 더해준다.)

0000 0000 1001 01100000 (왼쪽으로 1비트 시프트)

0000 0001 0010 11000000 (왼쪽으로 1비트 시프트)

0000 0010 0101 10000000 (BCD코드 첫째자리가 5로 5이상이므로 3을 더해준다.)

0000 0010 1000 10000000 (왼쪽으로 1비트 시프트)

0000 0101 0001 00000000 (BCD코드 둘째자리가 5로 5이상이므로 3을 더해준다.)

0000 1000 0001 00000000 (왼쪽으로 1비트 시프트)

0001 0000 0010 00000000 (왼쪽으로 1비트 시프트)

0010 0000 0100 00000000 (변환 끝)

이진수 11001100은 204이다. 성공적으로 변환되었다는 것을 알수 있다.

그렇다면 어떻게 이런일이 가능한걸까? 각 자리가 4비트씩 묶여있으므로 16진수로 변환해서 파악해보자.

0 0 0 CC

왼쪽으로 1비트 시프트 하는 것은 2를 곱하는 것과 같다.
0 0 1 98
0 0 3 30
0 0 6 60
여기서 6에다가 3을 더해준다. 왜일까?
16진수에서는 8이상의 수에다가 2를 곱하면 윗자리로 수가 받아올려진다.
하지만 10진수에서는 5이상의 수에다가 2를 곱해야 윗자리로 수가 받아올려진다.
따라서 5이상의 수들에 3을 더해서 8이상의 수들로 만들어주면, 2를 곱했을때 십진수와 같은 꼴로 자리올림이 일어난다. 이게 5이상의 수들에 3을 더하는 이유다.
0 0 9 60
0 1 2 C0
0 2 5 80
0 2 8 80
0 5 1 00
0 8 1 00
1 0 2 00
2 0 4 00
0xCC==204