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

全部博文(32)

文章存档

2012年(32)

分类: C/C++

2012-03-11 13:37:31

代码下载:
git clone git://git.code.sf.net/p/cutility/code cutility-code
长整数总共有两个文件一个为big_integer.h,一个为big_integer.c

(一)简介
关于大数,书中是这样谈到了,见下图:
上面是说,任何一个数,可以用不同的表示方法来表于,最常用是10进制,而对于机器来说,二进制是最好的。假设选定基数b(进制),则任何的正数,都可以唯一的被表示出来。
(二)数据结构:

  1. typedef unsigned short b_unit;
  2. typedef short sb_unit;
  3. typedef unsigned long twob_unit;
  4. typedef long stwob_unit;
  5. struct big_integer
  6. {
  7.     int b_len;
  8.     b_unit b_val[0];
  9. };
  10. typedef struct big_integer BGInteger;
(1)成员说明:

上面定义了一个结构体struct big_integer,为了后面表示方面,用typedef进行了类型重定义为BGInteger。
BGInteger总共有两个成员:
  1. b_len的绝对值表示数组b_val的长度,如果b_len为负,则该长整数为负数,如果正,则长整数为正数,如果为0则表示长整数的值为0
  2. b_val是一个一维数据,用于保存长整数的值,b_val[0]存低位,b_val[b_len-1] 最高位。

不同大小的长整数,所需要的存储空间也不一样,所以不能在定义时就确定下来。所以在BIGinteger中b_val数组的脚标为0,这么方法称为柔性数组,在C99中有这样的说明:结构中的最后一个元素允许是未知大小的数组,这就叫做柔性数组成员,但结构中的柔性数组成员前面必须至少一个其他成员。柔性数组成员允许结构中包含一个大小可变的数组。sizeof返回的这种结构大小不包括柔性数组的内存。包含柔性数组成员的结构用malloc ()函数进行内存的动态分配,并且分配的内存应该大于结构的大小,以适应柔性数组的预期大小。

(2)数据的存储方式

在网上搜一下关于长整数的资料,大部分都是以十进制为基础,用一个char的组数或者是链表来保存数中的每一位。这种存储方式好处在于直观,加,减,乘,除易于实现,并且容易从输入流中构造数据结构。但是这种方式的缺点在于位运算的实现难度大,就算能实现效率也不高。
计算机是以二进制运算为基础,为了保持一致性,BGInteger与采用二进制来存储数据。b_val是unsigned short 类型的数组,unsigned short类型可以保存16位数据,但是为了后面运算方便,只使用了b_val每一个元素的低15位。

例如,十进制"55555555555"转化为二进制后的值为:"110011101111010111101000000011100011",总共需36比特来保存,b_val中一个元素可以使用15比特,所以需有3个元素,即b_len的值为3。b_val[0]保存0...14位,b_val[2]保存15...29位,b_val[2]保存30...35位。如下图:

(3)长整数的值:
其中:其中 len为b_len,value为b_val,shift的值为15
(4)编码方式

有符号数有三种表示法:原码,反码,补码。但在计算机系统中,数值一律用补码来表示(存储)。 主要原因:使用补码,可以将符号位和其它位统一处理;同时,减法也可按加法来处理。但是BIGInteger中数值使用的是原码来表示。其中符号位通过b_len来判断:
  1. b_len为负,则表示该长整数是一个负数
  2. b_len为正,则表示该长整数为一正数
  3. b_len为0,表示长整数的值为0
同时b_len的绝对值也表示数组b_val的长度

(三)接口:

因为长整数需要实现加,减,乘,除,求余,左移,右移,与,或,异或,求反,大小比较。所以需要实现下面几个接口
说明:下面函数的参数不能NULL,否则返回结果为未知
(1)构造函数
BGInteger有5种创建方法分别为:
  1. BGInteger* bg_create_from_int(int value);
  2. BGInteger* bg_create_from_octstr(char* str);
  3. BGInteger* bg_create_from_binstr(char* str);
  4. BGInteger* bg_create_from_decstr(char* str);
  5. BGInteger* bg_create_from_hexstr(char* str);
其中:
  1. bg_create_from_int表示从一个整数中生成BGIngter。
  2. bg_create_from_binstr表示从二进制字符串中读取数据,然后返回BGInteger。但要求能存在’0‘或者’1‘两种字符,否则不能返回正确的结果。
  3. bg_create_from_octstr表示从八进制字符串中读取数据,然后返回BGInteger。但要求能存在’0‘到’7‘这8种字符,否则不能返回正确的结果。
  4. bg_create_from_decstr表示从十进制字符串中读取数据,然后返回BGInteger。但要求能存在’0‘到’9‘这10种字符,否则不能返回正确的结果。
  5. bg_create_from_hexstr表示从十六进制字符串中读取数据,然后返回BGInteger。但要求能存在’0‘到’9‘和'a'到'f'这16种字符,否则不能返回正确的结果。
(2)加,减
  1. BGInteger* bg_plus(BGInteger* left, BGInteger* right);
  2. BGInteger* bg_minus(BGInteger* left,BGInteger* right);
其中:
  1. bg_plus返回两长整数相加的结果;
  2. bg_minus返回两长整数相减的结果。
(3)乘,除,求除
  1. BGInteger* bg_mul(BGInteger* left,BGInteger* right);
  2. BGInteger* bg_div(BGInteger* left,BGInteger* right);
  3. BGInteger* bg_mod(BGInteger* left,BGInteger* right);
其中:
  1. bg_mul返回两长整数相乘的结果;
  2. bg_div返回两长整数相除的结果,并且要求参数right值不能为0,如果为0,则返回NULL
  3. bg_mod对两长整数求余,返回值为余数,要求参数right值不能为0,如果为0,则返回NULL
(4)左移,右移
  1. BGInteger* bg_lshift(BGInteger* left,BGInteger* right);
  2. BGInteger* bg_rshift(BGInteger* left,BGInteger* right);
其中:
  1. bg_lshift返回值为参数left左移right位后的值,要求参数right不参为负数,并且大能大于2^31。否则返回结果为NULL
  2. bg_lshift返回值为参数left右移right位后的值,要求参数right不参为负数,并且大能大于2^31。否则返回结果为NULL
(5)与,或,异或,求反
  1. BGInteger* bg_and(BGInteger* left,BGInteger* right);
  2. BGInteger* bg_or(BGInteger* left,BGInteger* right);
  3. BGInteger* bg_xor(BGInteger* left,BGInteger* right);
  4. BGInteger* bg_invert(BGInteger* bg);
其中:
  1. bg_and返回两长整数相与的结果
  2. bg_or返回两长整数相或的结果
  3. bg_xor返回两长整数异或的结果
  4. bg_invert返回值为对参数bg取反后的结果
(6)大小比较
  1. int bg_cmp(BGInteger* left,BGInteger* right);
其中:
  1. bg_cmp表示比较两个长整数的大小,如果leftright返回值为1
(7)内存释放
  1. void bg_free(BGInteger* bg)
其中:
  1. bg_free释放bg占用的内存空间
(8)输出长整数
  1. void bg_print_dec(BGInteger* bg);
  2. void bg_print_bin(BGInteger* bg);
其中:
  1. bg_print_dec是以十进制输出长整数的数值
  2. bg_print_bin以二进制输出长整数的数值

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