长整数－－加法与减法

代码下载：

git clone git://git.code.sf.net/p/cutility/code cutility-code

长整数总共有两个文件一个为big_integer.h，一个为big_integer.c

在看这一篇文章这前你需要了解长整数的数据结构

(一)简介

在32位机上，如果要实现64位加法运算，可以用汇编中带进位的加法指令来实现

例如，假设有两个64位数Num_a和Num_b，其中：

1. Num_a的值保存在数组a中，其中a[0]保存低32位，a[1]保存高32位；
2. Num_b的值保存在数组b中，其中b[0]保存低32位，b[1]保存高32位；
3. Num_a+Num_b的结果为Num_c保存在数组c中，同样c[0]保存低32位，c[1]保存高32位

汇编指令为：

add c[0] a[0] b[0] #c[0]=a[0]+b[0]
adc c[1] a[1] b[1] #c[1]=a[1]+b[1]+carry ,carry为进位标志

但是BGInteger使用的是C语言，不能直接获取进位标志，虽然可以嵌入汇编，用起来使复杂。在前面数据结构与接口那篇提到BGInteger成员b_val是一个16位的数组，但只使用了数组中每一个元素的15位。这所以这样做是因为，第16位在做加法时，可以用于表示进位标志。

例如，两个数数a与b，求c=a+b ，其中：

1. a＝"94059"，转化为二进制为"10110111101101011"，占17位，即需要两个b_val元素，每一个b_val元素可以保存15位，即a.b_val[0]="110111101101011"  , a.b_val[1]="10"
2. b="912926"，转化为二进制为"11011110111000011110"，占20位，同样也需要2个b_val元素，即b.b_val[0]="110111000011110" , b.b_val[1]="11011"

相加过程为：

(1) a的低15位与b的低15位相加，得到一个16位的数"1101110110001001"，如下图：

上图两个15位数相加，得到结果是一个16位的数，低15位用于赋值给c.b_val[0]，最高位用于表示进位标志，为1，表明产生了进位，要获取该进位，只需要把16位的结果左移15位，用C语言实现为：

b_unit val=a.b_val[0]+b.b_val[1];
c.b_val[0]=val&((b_unit)((1<<15)-1));
carry=val>>15;

(2) a的高位"10" 与 b的高位"11011" 并且连同进位一起相加得，如下图：

把结果11110赋值结c.b_val[1]。

得到结果c有两个b_val元素，c.b_val[1]="11110"，c.b_val[0]="101110110001001"，总共20位，转换为十进制为"1006985"，刚好为"94059"+"912926"相加的值。

(二)加法与减法

在实现加法与减法之前，先实现两个长整数绝对值的加法与减法。

(1)长整数绝对值加法

关于正长整数找加法算法，描述为：

上面的算法描述的是两个正整数相加的方法，其中的c表示进位，进位的初始值为零，先从两数的低位和与进位相加开始，依次到高位。

代码实现为：

static BGInteger* abs_plus(BGInteger* l,BGInteger* r)
{
    int l_len=abs(l->b_len);
    int r_len=abs(r->b_len);

    /*保证绝对值大的数在左边*/
    if(l_len<r_len)
    {
        BGInteger* tempb=l;
        l=r;
        r=tempb;
        int tempi=l_len;
        l_len=r_len;
        r_len=tempi;
    }
    b_unit* l_val=l->b_val;
    b_unit* r_val=r->b_val;

    /*两个k位的数相加,结果不可能大于k+1位，所以只需要为结果分配l_len+1的空间即足够*/
    BGInteger* ret=bg_malloc(l_len+1);
    b_unit* t_val=ret->b_val;

    b_unit carry=0;  /*进位标志*/
    int i;
    for(i=0;i<r_len;i++)
    {
        carry=l_val[i]+r_val[i]+carry;   /*带进位的加法*/
        t_val[i]=carry&MASK;      /*把低15位赋值组t_val[i]*/
        carry>>=SHIFT;           /*获取进位*/
    }
    for(;i<l_len;i++)
    {
        carry=l_val[i]+carry;
        t_val[i]=carry&MASK;
        carry>>=SHIFT;
    }
    t_val[i]=carry;
    bg_format_len(ret);   /*两个k位数相加可能为k+1位，当然也可能为k位，确定最终结果的位数*/
    return ret;
}

其中：因为BGInteger使用的是原码的编码方式，所以负数转换为正数只需要对b_len求绝对值即可

(2)长整数绝对值减法

正长整数的减法算法，描述为：

上面图片中是两个正长整数x，y相减，并且x>y。其中c表示借位。

代码实现为：

static BGInteger* abs_minus(BGInteger* l,BGInteger* r)
{
    int l_len=abs(l->b_len);
    int r_len=abs(r->b_len);
    int sign=1;
    /*保证绝对值大的数在左边*/
    if(l_len<r_len)
    {
        BGInteger* tempb=l;
        l=r;
        r=tempb;
        int tempi=l_len;
        l_len=r_len;
        r_len=tempi;
        sign=-1;
    }
    else if(l_len==r_len)
    {
        /*两个数的位数相同，所以需要进一步判断两数大小*/
        while(l_len&&(l->b_val[l_len-1]==r->b_val[l_len-1])) l_len--;
        if(l_len==0)
        {
           return bg_create_zero();  /*两数相等，返加0*/
        }
        r_len=l_len;      /*高位相等，所以只需要对不同的位求差即可*/
        if(l->b_val[l_len-1]<r->b_val[r_len-1])  /*保证绝对值大的数在左边*/
        {
            BGInteger* tempb=l;
            l=r;
            r=tempb;
            sign=-1;
        }
    }


    b_unit* l_val=l->b_val;
    b_unit* r_val=r->b_val;

    /*k位减n位的数,并且k>n，则差不会大于k位,所以分配l_len长度即足够*/
    BGInteger* ret=bg_malloc(l_len);
    b_unit* t_val=ret->b_val;

    int i;
    b_unit borrow=0;     /*借位标志，初始值为0*/
    for(i=0;i<r_len;i++)
    {
        borrow=l_val[i]-r_val[i]-borrow;
        t_val[i]=borrow&MASK;    /*低15位赋值给t_val[i]*/
        borrow=(borrow>>SHIFT)&1;  /*获取进位标志*/
    }
    for(;i<l_len;i++)
    {
        borrow=l_val[i]-borrow;
        t_val[i]=borrow&MASK;
        borrow=(borrow>>SHIFT)&1;
    }
    if(sign==-1)
    {
        self_negative(ret);  /*如果是小数减大数，结果应该为负*/
    }

    bg_format_len(ret);
    return ret;
}

(3)加法：

在前面，只是实现了两个长整数绝对值加法与减法，如果正数与负数相加还不能直接得到结果，还需要做一些转换。

假设两个数l与r，abs(l)表示数l的绝对值，abs(r)表示数r的绝对值，他们相加结果为c

1. 如果l<0,r<0，则c=-(abs(l)+abs(r))
2. 如果l<0,r>=0，则c=-abs(l)+abs(r)=-(abs(l)-abs(r))
3. 如果l>=0,r<0，则c=abs(l)-abs(r)
4. 如果l>=0,r<0，则c=abs(l)+abs(r)

加法的代码为：

BGInteger* bg_plus(BGInteger* l,BGInteger* r)
{
    BGInteger* ret=0;
    if(l->b_len<0)
    {
        if(r->b_len<0)
        {
            /* l<0, r<0
             * ret=-(abs(l)+abs(r))
             */
            ret=abs_plus(l,r);
            self_negative(ret);
        }
        else
        {
            /*l<0,r>=0
             * ret=-(abs(r)-abs(r))
             */
            ret=abs_minus(l,r);
            self_negative(ret);
        }
    }
    else
    {
        if(r->b_len<0)
        {
            /* l>=0,r<0
             * ret=abs(l)-abs(r)
             */
            ret=abs_minus(l,r);
        }
        else
        {
            /* l>=0,r>=0
             * ret=abs(l)+abs(r)
             */
            ret=abs_plus(l,r);
        }
    }
    return ret;
}

(4)减法

同加法一样，减法也需要一定转换才能得到正确的结果。

假设两个数l与r，abs(l)表示数l的绝对值，abs(r)表示数r的绝对值，他们相加结果为c

1. 如果l<0,r<0，则c=-abs(l)-(-abs(r))=-(abs(l)-abs(r))
2. 如果l<0,r>=0，则c=-abs(l)-abs(r)=-(abs(l)+abs(r))
3. 如果l>=0,r<0，则c=abs(l)-(-abs(r)=abs(l)+abs(r)
4. 如果l>=0,r>=0，则c=abs(l)-abs(r)

代码为：

BGInteger* bg_minus(BGInteger* l,BGInteger* r)
{
    BGInteger* ret=0;
    if(l->b_len<0)
    {
        if(r->b_len<0)
        {
            /* l<0 ,r<0
             * l-r=-abs(l)-(-abs(r))=-(abs(l)-abs(r));
             */
            ret=abs_minus(l,r);
            self_negative(ret);
        }
        else
        {
            /* l<0,r>=0
             * l-r=-abs(l)-abs(r)=-(abs(l)+abs(r));
             */
            ret=abs_plus(l,r);
            self_negative(ret);
        }
    }
    else
    {
        if(r->b_len<0)
        {
            /* l>=0 ,r <0
             * l-r=abs(l)-(-abs(r))=abs(l)+abs(r);
             */
            ret=abs_plus(l,r);

        }
        else
        {
            /* l>=0, r>=0
             * l-r=abs(l)-abs(r)
             */
            ret=abs_minus(l,r);

        }

    }
    return ret;
}