1. BCD码的求和
BCD码使用4位二进制数来表示十进制中0~9这10个数的数码。例如，十进制的237，其BCD码就是0010_0011_0111，但是其二进制是1110_1101。
我们先来研究两个4位的BCD码相加的情况。设这两个BCD码对应的十进制是a,b，其中a,b∈{0,1,2,...,9}。此时只有3种情况：
- 0≤a+b≤9
- 10≤a+b≤15
- 16≤a+b≤18
也就是说：
- 对于第一种情况，结果本身就是对应的BCD码。例如，
0100+0101=1001，即4+5=9； - 对于第二种情况，其结果对于4位运算来说没有产生进位，但是结果超过了BCD码表示的范围（因为4位BCD码最多表示9）。例如，5+8=13，
0101+1000=1101 - 对于第三种情况，其结果对于4位运算来说不仅产生了进位，而且其结果也超过了BCD码表示的范围。例如，4+13=17，
0100+1101=1_0001
第一种情况显然不需要再修正。
第二种情况，例如，5+8=13，我们希望得到BCD码是0001_0011，但是运算结果1101，因此如果我们加上了6，就可以得到正确结果：1101+0110=0001_0011。这是因为，十进制是逢十进一，但是4位BCD加法，在看作是二进制数做加法时，是逢十六进一。因此，如果结果是10≤a+b≤15，加上6以后就是16+0≤a+b+6≤16+5，此时因为逢十六进一的原因，就得到了结果1_0≤[a+b+6]≤1_5，这个结果就是对的。
第三种情况，因为16≤a+b≤18，逢十六进一后，我们得到了1_0≤[a+b]≤1_2，为了使结果正确，如果我们加上一个修正值6，就得到1_6≤[a+b+6]≤1_8，从而结果也变得正确。
综上所述，如果两个BCD码相加：
- 如果结果小于9，则不做操作
- 如果结果大于9，则需要加上6作为修正值
考虑一个例子，比如 35+99=134。35和99的BCD码分别是0011_0101和1001_1001。先计算低4位：0101+1001=1110，因为这个值大于9，因此加上6作为修正：1110+0110=1_0100。现在计算高四位，同时注意到还有一个进位：0011+1001+0001=1101，这个值还是大于9，加上6，得到1101+0110=1_0011。因此最终结果是1_0011_0100，这刚好就是134的BCD码。
我们之所以能够安全地加上进位，是因为BCD加法比照的就是十进制的加法，只不过前者是4位为一个单位，而后者是以1位数字作为一个单位。加上修正值后，BCD加法的进位就相当于十进制加法的进位。图示如下：
2. 二进制转BCD码
给定一个二进制数，要转BCD码。一个常用算法就是不断将该数除以10，以此依次分解出个位、十位、百位……上的数字，这些数字的4位二进制数就是对应的BCD。但是这样的算法需要不断做除法操作十分的麻烦。我们可以使用名为加三左移法来完成。
这个算法基于以下的事实：
- 一个数乘以2，相当于其二进制左移1位
- 两个BCD码相加，如果结果大于9，需要加上6作为修正
一个n位二进制数，其展开是
如果使用秦九韶算法的嵌套形式写法，可以写成：
或者若令
则
如果使用这种形式，我们先计算的是
，然后是
，然后是
，……，最后是
。
注意到就是把
左移1位，这样就会在最右边空出一个位，之后再加
就是用
填充这个最低位，从而我们得到了
。不断左移，最终就能得到
，现在我们来设计一个算法使得左移结束后能得到对应的BCD码。
设是一个无限长的、初始状态为所有位都是0的理想寄存器，
是欲转换的数。我们使用下面的归纳法来构造证明我们通过不断左移最终能够得到存储在
中的
对应的BCD码：
初始：
左移
进入
，通过若干运算后，
的BCD码。这个显然是成立的，因为
是1位（不是0就是1，对应BCD码就是本身），将其左移进
假设：设某一时刻，已经将
左移入
的BCD码
归纳：现在准备移入
，我们希望这个步骤结束后，
的BCD码。因为此时
，即将
，设
，做如下处理：
- 如果从
开始之后全部为0，则过程结束
- 否则如果
，则转第4步
- 否则，令
，保留4位
- 置
，转第1步
为什么要加3呢？这是因为如果
，那么加法结果要加修正值6，也就是
，这等价于
；如果
，从而加3不会产生进位。如此处理后，将
的BCD码。现在，因为乘以2的关系，
，于是加上
。从而，得到的就是
由数学归纳原理，移动len(h)次后，我们最终可以得到的BCD码。
作为一个例子，考虑使用该算法将的二进制
1000_0110转为BCD码：
- 初始：R=
..._0000_0000,h=1000_0110（下面使用#作为占位符） - R中的
..._0000_0001,h=0000_110# - R中的
..._0000_0010,h=0001_10## - R中的
..._0000_0100,h=0011_0### - R中的
..._0000_1000,h=0110_#### - R中的
，对其做加3处理得到R=
..._0000_1011。R左移1位，h左移一位进入R：R=..._0001_0110,h=110#_#### - R中的
，对其做加3处理得到R=
..._0001_1001。R左移1位，h左移一位进入R：R=..._0011_0011,h=10##_#### - R中的
..._0110_0111,h=0###_#### - R中的
，对其都做加3处理得到R=
..._1001_1010。R左移1位，h左移一位进入R：R=..._0001_0011_0100,h=####_####
现在，已经全部移入，此时
的值就是
0001_0011_0100，它就是的BCD码。
C语言的算法如下：
#include<stdio.h>
#define N 50
#define DIGITS_NUM 8*sizeof(byte_t)
typedef char byte_t;
byte_t regstr[N];
void resetRegstr(){
for(int i=0;i<N;i++) regstr[i]=0;
}
void show8421bcd(){
int i=0;
for(i=0;i<N;i++){
if(regstr[i]!=0) break;
}
if(i==N) {
printf("0\n");
return;
}
for(;i<N;i++){
byte_t unit=regstr[i];
for(int j=0;j<DIGITS_NUM/4;j++){
printf("%d",(unit>>(4*(DIGITS_NUM/4-j-1)))&0xF);
}
}
printf("\n");
}
byte_t _processUnit(byte_t unit){
byte_t newval=0;
for(int j=0;j<DIGITS_NUM/4;j++){
int val=0xF&(unit>>(4*j));
newval|=(val+(val>4?3:0))<<(4*j);
}
return newval;
}
int to8421bcd(byte_t *num,int n){
resetRegstr();
for(int k=0;k<n;k++){
byte_t digit=num[k];
for(int i=DIGITS_NUM-1;i>-1;i--){
byte_t bi=(digit>>i)&0x1;
for(int j=N-1;j>-1;j--){
byte_t bi_=_processUnit(regstr[j]);
regstr[j]=(bi_<<1)|bi;
bi_=(bi_>>(DIGITS_NUM-1))&0x1;
if(bi_==1&&j==0) return 0;
bi=bi_;
}
}
}
return 1;
}
void main(){
byte_t nums[]={/*2,321,973,245,437,681,127 */
0x20,0x39,0x4E,0x5D,0x48,0x46,0x1D,0xE7
};
int ok=to8421bcd(nums,8);
if(!ok){
printf("something wrong...\n");
}else{
show8421bcd();
}
}
网友评论