Chinaunix首页 | 论坛 | 博客
  • 博客访问: 236476
  • 博文数量: 32
  • 博客积分: 424
  • 博客等级: 准尉
  • 技术积分: 465
  • 用 户 组: 普通用户
  • 注册时间: 2012-03-02 10:23
文章分类

全部博文(32)

文章存档

2012年(32)

分类: C/C++

2012-03-11 15:48:11

代码下载:
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位
汇编指令为:
  1. add c[0] a[0] b[0] #c[0]=a[0]+b[0]
  2. 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语言实现为:
  1. b_unit val=a.b_val[0]+b.b_val[1];
  2. c.b_val[0]=val&((b_unit)((1<<15)-1));
  3. 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表示进位,进位的初始值为零,先从两数的低位和与进位相加开始,依次到高位。
代码实现为:
  1. static BGInteger* abs_plus(BGInteger* l,BGInteger* r)
  2. {
  3.     int l_len=abs(l->b_len);
  4.     int r_len=abs(r->b_len);

  5.     /*保证绝对值大的数在左边*/
  6.     if(l_len<r_len)
  7.     {
  8.         BGInteger* tempb=l;
  9.         l=r;
  10.         r=tempb;
  11.         int tempi=l_len;
  12.         l_len=r_len;
  13.         r_len=tempi;
  14.     }
  15.     b_unit* l_val=l->b_val;
  16.     b_unit* r_val=r->b_val;
  17.  
  18.     /*两个k位的数相加,结果不可能大于k+1位,所以只需要为结果分配l_len+1的空间即足够*/
  19.     BGInteger* ret=bg_malloc(l_len+1);
  20.     b_unit* t_val=ret->b_val;

  21.     b_unit carry=0;  /*进位标志*/
  22.     int i;
  23.     for(i=0;i<r_len;i++)
  24.     {
  25.         carry=l_val[i]+r_val[i]+carry;   /*带进位的加法*/
  26.         t_val[i]=carry&MASK;      /*把低15位赋值组t_val[i]*/
  27.         carry>>=SHIFT;           /*获取进位*/
  28.     }
  29.     for(;i<l_len;i++)
  30.     {
  31.         carry=l_val[i]+carry;
  32.         t_val[i]=carry&MASK;
  33.         carry>>=SHIFT;
  34.     }
  35.     t_val[i]=carry;
  36.     bg_format_len(ret);   /*两个k位数相加可能为k+1位,当然也可能为k位,确定最终结果的位数*/
  37.     return ret;
  38. }
其中:因为BGInteger使用的是原码的编码方式,所以负数转换为正数只需要对b_len求绝对值即可

(2)长整数绝对值减法

正长整数的减法算法,描述为:

上面图片中是两个正长整数x,y相减,并且x>y。其中c表示借位。
代码实现为:
  1. static BGInteger* abs_minus(BGInteger* l,BGInteger* r)
  2. {
  3.     int l_len=abs(l->b_len);
  4.     int r_len=abs(r->b_len);
  5.     int sign=1;
  6.     /*保证绝对值大的数在左边*/
  7.     if(l_len<r_len)
  8.     {
  9.         BGInteger* tempb=l;
  10.         l=r;
  11.         r=tempb;
  12.         int tempi=l_len;
  13.         l_len=r_len;
  14.         r_len=tempi;
  15.         sign=-1;
  16.     }
  17.     else if(l_len==r_len)
  18.     {
  19.         /*两个数的位数相同,所以需要进一步判断两数大小*/
  20.         while(l_len&&(l->b_val[l_len-1]==r->b_val[l_len-1])) l_len--;
  21.         if(l_len==0)
  22.         {
  23.          return bg_create_zero();  /*两数相等,返加0*/
  24.         }
  25.         r_len=l_len;      /*高位相等,所以只需要对不同的位求差即可*/
  26.         if(l->b_val[l_len-1]<r->b_val[r_len-1])  /*保证绝对值大的数在左边*/
  27.         {
  28.             BGInteger* tempb=l;
  29.             l=r;
  30.             r=tempb;
  31.             sign=-1;
  32.         }
  33.     }


  34.     b_unit* l_val=l->b_val;
  35.     b_unit* r_val=r->b_val;
  36.     
  37.     /*k位减n位的数,并且k>n,则差不会大于k位,所以分配l_len长度即足够*/
  38.     BGInteger* ret=bg_malloc(l_len);
  39.     b_unit* t_val=ret->b_val;

  40.     int i;
  41.     b_unit borrow=0;     /*借位标志,初始值为0*/
  42.     for(i=0;i<r_len;i++)
  43.     {
  44.         borrow=l_val[i]-r_val[i]-borrow;
  45.         t_val[i]=borrow&MASK;    /*低15位赋值给t_val[i]*/
  46.         borrow=(borrow>>SHIFT)&1;  /*获取进位标志*/
  47.     }
  48.     for(;i<l_len;i++)
  49.     {
  50.         borrow=l_val[i]-borrow;
  51.         t_val[i]=borrow&MASK;
  52.         borrow=(borrow>>SHIFT)&1;
  53.     }
  54.     if(sign==-1)
  55.     {
  56.         self_negative(ret);  /*如果是小数减大数,结果应该为负*/
  57.     }

  58.     bg_format_len(ret);
  59.     return ret;
  60. }
(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)
加法的代码为:
  1. BGInteger* bg_plus(BGInteger* l,BGInteger* r)
  2. {
  3.     BGInteger* ret=0;
  4.     if(l->b_len<0)
  5.     {
  6.         if(r->b_len<0)
  7.         {
  8.             /* l<0, r<0
  9.              * ret=-(abs(l)+abs(r))
  10.              */
  11.             ret=abs_plus(l,r);
  12.             self_negative(ret);
  13.         }
  14.         else
  15.         {
  16.             /*l<0,r>=0
  17.              * ret=-(abs(r)-abs(r))
  18.              */
  19.             ret=abs_minus(l,r);
  20.             self_negative(ret);
  21.         }
  22.     }
  23.     else
  24.     {
  25.         if(r->b_len<0)
  26.         {
  27.             /* l>=0,r<0
  28.              * ret=abs(l)-abs(r)
  29.              */
  30.             ret=abs_minus(l,r);
  31.         }
  32.         else
  33.         {
  34.             /* l>=0,r>=0
  35.              * ret=abs(l)+abs(r)
  36.              */
  37.             ret=abs_plus(l,r);
  38.         }
  39.     }
  40.     return ret;
  41. }
(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)
代码为:
  1. BGInteger* bg_minus(BGInteger* l,BGInteger* r)
  2. {
  3.     BGInteger* ret=0;
  4.     if(l->b_len<0)
  5.     {
  6.         if(r->b_len<0)
  7.         {
  8.             /* l<0 ,r<0
  9.              * l-r=-abs(l)-(-abs(r))=-(abs(l)-abs(r));
  10.              */
  11.             ret=abs_minus(l,r);
  12.             self_negative(ret);
  13.         }
  14.         else
  15.         {
  16.             /* l<0,r>=0
  17.              * l-r=-abs(l)-abs(r)=-(abs(l)+abs(r));
  18.              */
  19.             ret=abs_plus(l,r);
  20.             self_negative(ret);
  21.         }
  22.     }
  23.     else
  24.     {
  25.         if(r->b_len<0)
  26.         {
  27.             /* l>=0 ,r <0
  28.              * l-r=abs(l)-(-abs(r))=abs(l)+abs(r);
  29.              */
  30.             ret=abs_plus(l,r);

  31.         }
  32.         else
  33.         {
  34.             /* l>=0, r>=0
  35.              * l-r=abs(l)-abs(r)
  36.              */
  37.             ret=abs_minus(l,r);

  38.         }

  39.     }
  40.     return ret;
  41. }



阅读(2863) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~