长整数－－数据结构与接口

4386阅读　0评论2012-03-11　NosicLin
分类：C/C++

代码下载：
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以二进制输出长整数的数值

上一篇：Redy词法分析--综合识别
下一篇：长整数－－加法与减法