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

代码下载：

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

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

(一)简介

关于大数，书中是这样谈到了，见下图：

上面是说，任何一个数，可以用不同的表示方法来表于，最常用是10进制，而对于机器来说，二进制是最好的。假设选定基数b（进制），则任何的正数，都可以唯一的被表示出来。

(二)数据结构：

typedef unsigned short b_unit;
typedef short sb_unit;
typedef unsigned long twob_unit;
typedef long stwob_unit;
struct big_integer
{
    int b_len;
    b_unit b_val[0];
};
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种创建方法分别为：

BGInteger* bg_create_from_int(int value);
BGInteger* bg_create_from_octstr(char* str);
BGInteger* bg_create_from_binstr(char* str);
BGInteger* bg_create_from_decstr(char* str);
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)加，减

BGInteger* bg_plus(BGInteger* left, BGInteger* right);
BGInteger* bg_minus(BGInteger* left,BGInteger* right);

其中：

1. bg_plus返回两长整数相加的结果；
2. bg_minus返回两长整数相减的结果。

(3)乘，除，求除

BGInteger* bg_mul(BGInteger* left,BGInteger* right);
BGInteger* bg_div(BGInteger* left,BGInteger* right);
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)左移，右移

BGInteger* bg_lshift(BGInteger* left,BGInteger* right);
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)与，或，异或，求反

BGInteger* bg_and(BGInteger* left,BGInteger* right);
BGInteger* bg_or(BGInteger* left,BGInteger* right);
BGInteger* bg_xor(BGInteger* left,BGInteger* right);
BGInteger* bg_invert(BGInteger* bg);

其中：

1. bg_and返回两长整数相与的结果
2. bg_or返回两长整数相或的结果
3. bg_xor返回两长整数异或的结果
4. bg_invert返回值为对参数bg取反后的结果

(6)大小比较

int bg_cmp(BGInteger* left,BGInteger* right);

其中：

1. bg_cmp表示比较两个长整数的大小，如果leftright返回值为1

(7)内存释放

void bg_free(BGInteger* bg)

其中：

1. bg_free释放bg占用的内存空间

(8)输出长整数

void bg_print_dec(BGInteger* bg);
void bg_print_bin(BGInteger* bg);

其中:

1. bg_print_dec是以十进制输出长整数的数值
2. bg_print_bin以二进制输出长整数的数值