从大数运算所想到的

发布时间：2020-12-14 03:57:28 所属栏目：大数据来源：网络整理

导读：[cpp] ? view plain copy #define?SHRT_MIN????(-32768)????????/*?minimum?(signed)?short?value?*/ ?? #define?SHRT_MAX??????32767?????????/*?maximum?(signed)?short?value?*/ ?? #define?USHRT_MAX?????0xffff????????/*?maximum?unsigned?short?value

[cpp]? 
   view plain 
   copy 
    
   
 #define?SHRT_MIN????(-32768)????????/*?minimum?(signed)?short?value?*/??
 #define?SHRT_MAX??????32767?????????/*?maximum?(signed)?short?value?*/??
 #define?USHRT_MAX?????0xffff????????/*?maximum?unsigned?short?value?*/??
 #define?INT_MIN?????(-2147483647?-?1)?/*?minimum?(signed)?int?value?*/??
 #define?INT_MAX???????2147483647????/*?maximum?(signed)?int?value?*/??
 #define?UINT_MAX??????0xffffffff????/*?maximum?unsigned?int?value?*/??
 #define?LONG_MIN????(-2147483647L?-?1)?/*?minimum?(signed)?long?value?*/??
 #define?LONG_MAX??????2147483647L???/*?maximum?(signed)?long?value?*/??
 #define?ULONG_MAX?????0xffffffffUL??/*?maximum?unsigned?long?value?*/??
 #define?LLONG_MAX?????9223372036854775807i64???????/*?maximum?signed?long?long?int?value?*/??
 #define?LLONG_MIN???(-9223372036854775807i64?-?1)??/*?minimum?signed?long?long?int?value?*/??
 #define?ULLONG_MAX????0xffffffffffffffffui64???????/*?maximum?unsigned?long?long?int?value?*/??

? ? ?

? ? ? ? ? ? ? ? ? /*写这篇文章之前，先说下一下背景，最初的时候，是准备写大数运算的，当然大数运算大家都写烂了，我自然是先借鉴了网上的诸多材料，才开始准备写。然而很不幸出师未捷身先死，还没有切入算法，就在准备工作上除了诸多问题，总算花了一个下午的时间解决了所有问题，接着今天的空闲时光写出这篇日志*/

大数运算，顾名思义，就是很大的数值的数进行一系列的运算。在C语言中定义的数据类型都是存在最大存储值的，在limits.h中有定义

从上面可以看出在C语言（在我的机器上）中可以存储的最大的数是unsigned?long?long?，也只能达到2^17-1的最大值。那么比这更大数怎么办呢？这就牵扯到大数怎么存储的问题了。使用相应的数据结构来存储数据，使用诸如数组，链表甚至是树来储存大数。就是解决这类问题的方法。最初的选择主要是在数组与链表中考虑。

如果使用链表的话，那么未来在计算数的时候，必须不停的移动指针，来完成计算，效率未免过低/*以上存疑*/。??那么使用数组呢？这时候就有许多东西需要考虑了，大尾存储，还是小尾存储。/*感兴趣的请自行google?little-endian和big-endian*/还是考虑对于运算的效率。对于进位运算而言，先从低位运算开始，将进位与后边的数进行运算，这个时候如果考虑小尾的存储方式更为的合理。但是在数组之中仍是标准的存储方式。

/*后来想想如果采用vector<long?long?>会不会更为的合理*/

copy 
    
   

#define?ARRAY_SIZE?10??

typedef?struct?LargeNumber??
{??
????int?digit;//实际利用到的位数??
????unsigned?long?int?array[ARRAY_SIZE];??
bool?flag;//用于标记符号位??
}*?PLargeNumber;??
???
???

在这里重点要聊一聊#define?ARRAY_SIZE?10

由于使用了宏定义，就会出现了一个重要的问题那就是数组的大小被固化，在这我们可以使用柔性数组

copy

struct?LargeNumber??

{??
????//实际利用到的位数??
????unsigned?int?array[];??
//用于标记符号位??
}*?PLargeNumber;??

有兴趣的朋友可以看看这个网址http://blog.csdn.net/ce123_zhouwei/article/details/8973073

当然在初始化的时候依旧要使用malloc?和realloc来扩展指针。当然嫌麻烦的可是直接使用指针unsined?long?long?*?array;/*好吧我承认，我应该在这里用vector*/

有了定义，就应该有初始化函数了

copy

bool?LargeNumberInit(PLargeNumber*?p)??

???
????*p?=?(PLargeNumber)?malloc?(sizeof(LargeNumber));??
????if(NULL?==?(*p))??
????????return?false;//创建失败??
else{??
for(int?i=0;?i!=ARRAY_SIZE;?i++){??
????????????(*p)->array[i]?=?0;??
????????}??
????????(*p)->length?=?0;??
true;??
????}??
}??

那么接下来的问题就到了如何读取数据了。既然是大数，那么传统的cin和sprinf?自然而然的被我放弃了/*其实我试过的无法单独的读取某个数*/。采用getchar()循环读取字符，在将字符转化位数字。

备选思路如下：

1.普大喜奔的位运算，16位的16进制数的unsigned?long?long?读取一个16进制数，采用左移的方式来读入一个数中。数组中的每一位都采用这样的方式来存储。

2.依旧是16位的做法这一次采用读取满一个16进制位，放入字符串中然后进行转化。

3.读取的是10进制数的字符，将其存入字符串中，读取满特定位数后，将其转化为数字。

最后本人采用了最后一种方法，原因在于在stdlib.h中有atoll
（）这样的转化函数/*后来证明这个方向是错的*/

copy

PLargeNumber?LargeNumberPutIn(PLargeNumber?PNum)??

int?i?=?0;??
int?number?=?0;??
char?buffer[NODESIZE+1];//定义的缓冲区存储输入的数字??
????buffer[NODESIZE]?=?'';??
????number?=?getchar();??
????if(number=='-')??
????????PNum->flag?=?false;??
else{??
true;??
????}??
do?{??
??????????
????????number?=?getchar();??
if?((number<='9')?&&?(number>='0')){??
????????????buffer[i%NODESIZE]?=?number;/*i%NODESIZE等于每次对应的缓冲区的位数*/??
????????????PNum->length++;??
??????????
????????if(((i%NODESIZE)==0)?&&?i!=0){??
/*每次读满NODESIZE位将数据刷入相对应的字节中*/??
????????????int?array_number?=?NODESIZE?-?i/NODESIZE?-?1;??
????????????PNum->array[array_number]?=?atoll(buffer);??
????????}??
????????i++;??
??????}????
while?((number!='#')?&&?(i!=NODESIZE*ARRAY_SIZE));??
return?PNum;??
}??
???

首先读取第一个数，判断其是否是符号位。再循环中执行下列过程读取19个数字放置在预先准备好的字符串数组中，在使用atoll函数转化。但是在VS中不存在atoll（）函数。同时使用atoll返回值是long?long?，

#define?LLONG_MAX?????9223372036854775807i64?

好吧我定义的的ARRAY_NODE_MAX是这个值

#define?ARRAY_NODE_MAX?9999999999999999999//比ULLMAX少一位

目测只能自己写这个函数了。

copy

unsigned?long?atoll(char*?buffer)??

const?int?longlength?=?10;??
long?tendigit?=?10000000000;??
long??number?=?0;??
int?buffer_length?=?strlen(buffer);??
int?begin_length?=?buffer_length?-?longlength;//buffer取出掉后十位后的长度??
if(buffer_length<=longlength)??
????????number?=?(unsigned?long)?atol?(buffer);??
else//如果大于10位的话??
????{??
????????char?dest_buffer[longlength+1];??
????????strcpy(dest_buffer,?buffer+begin_length);//单独取出后十位??
????????number?+=?atol(dest_buffer);??
int?i=0;?i!=longlength;?i++)?????????????????dest_buffer[i]?=?'';/*必须把缓冲区清空，避免上一次的数据污染*/??
???????memcpy(dest_buffer,buffer,??
???????????????????sizeof(char)*begin_length);//以后十位为终点取出前边几位??
????????number?+=?atol(dest_buffer)*tendigit;??
return?number;??
}??

就这样所有的准备工作都已经就绪，紧接着的就是大数运算咯。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!