学习笔记 - 关于非负大整数计算的一些想法

Posted by morouu on 2022-05-20
Estimated Reading Time 47 Minutes
Words 11.1k In Total
Viewed Times

关于大非负整数计算的一些想法


前言

就是说,关于吾等人在看 《算法分析与设计》 时坐大牢,随便找点其他的乐子当作兴趣玩玩了。不得说,现在个人的感受是,早知道当年还不如选算法,搞安全搞得头疼,说到底就是搞各种测试啥的,搞算法搞得头秃(起码头不疼 (●ˇ∀ˇ●)。

主要还是卷不动了

不妨就当作一些奇怪的想法,当作随笔写写看了。


绪论(瞎扯)

一些简单数值运算实例,比方说加法、乘法、幂次乘法啥的,其实归根到底还是对加法的灵活运用,个人的感觉(大概?)。这就像是说像一个很简单代码:

1
2
3
int a = 1;
bigInt N;
a = a + N;

以上这样看起来似乎非常非常的简单,但实际上如果再往深一层考虑的话是可以扯出很多东西来的。就这个 int a = 1 而言,显然是限定了这个变量 a 是一个 int 型,也就是熟知的数据类型。

数据结构 中对高级语言的数据类型的解释是 一组性质相同的值的集合和定义在该值集上的一组方法的总称 。从中可知,这个 值集 是有范围的 ,而且根据操作系统而定。一般来说,如果是大于等于 32 位系统, int 类型的大小为 4 个字节;对于小于 32 位系统, int 类型的大小为 2 个字节(这也是为啥有些C教材里面的关于 int 类型的答案是 2 字节长度)。

当然,就目前来说吾等人的想法并不想深究这个玩意,只是表示假设想写的所有内容都是以 64 位为例(相当于指针大小为 8 位大小,可以用 unsigned long long int 来强转指针的歪门邪道 随便说说)。另外下述的所有 long 实际上和 long int 以及 int 一致的,都是 4 个字节,而 long long int8 个字节。回归来说,上面的 int a 的最大大小为 4 个字节,而又由于这是一个有符号数,则第 1 位用来表示符号,这也就是其值集为整数 -2^31 ~ 2^31-1 的原因, 这也就是什么 补码 反码 的内容了,比方说 负数值(原码) = 补码 - 1 AND 取反 ,当然,无论如何,符号位永远不变!

那么瞎扯完毕,对于 int a 运算的值的有效计算位数为 4 * 8 - 1(符号位) = 31 位,凡是无论多大的整数 N(位数很高的整数)都会自然而然的强行在化为 int a 类型的值集范围(假设看作强转成与 int 位数相同的类型)内进行运算,并且当 N 的位数 bit(N)bit(N) >= 8 时(不包括 N 的符号位)那么 a 的符号位也会被计算到,这实际上可以人为地将 N 的低 8 位看成 unsigned int 类型,所以说当所要计算的数足够大时,会改变原有数值如 a 的符号(溢出),这是不可接受的。

正因为高级程序设计语言所提供的 数据类型 在很多时候无法满足一些 “大宇宙” 问题(如某某曾对有关如何对全宇宙的所有事物进行排序时采用归并排序的荒谬思路),说简单点比如关于素数 P 的判定充要条件

image-20220520161057447

P 足够大时,阶乘的计算量可想而知(超过常规 数据类型 所能表示的大小);亦或是需要求一些比较大,但不完全大的数值,比如某些毫无意义的值 520 ^ 520 啥的,自定义一个 大整数 是很有必要的!


理论

简单加法

先从最最简单的加法运算来进行分析罢。

对于一个数,如先做以下赋值:

image-20220520161111203

这对所有人(九漏🐟除外)来说如果计算以下式子:

image-20220520161124313

简直就是随意随意呀。这里之所以能这么快得出答案是因为脑子已经习惯了 10 进制的计算(有志者或大佬除外),并且在计算机中对已给定的 数据类型 也有相关明确的计算规则,不需要人为的进行计算规则的实现。

但是!上面已经说了,高级程序设计语言给定的 数据类型 还不够!现在所给的 数据类型 (也就是Integer )并不是高级程序设计语言已经给定好的 数据类型 ,而是一个能表示很大很大(位数小于内存大小的位数)的数值的 数据类型 ,也就是说这是一个自定义的、只能用以存储人为给定数值的 数据类型 ,那就必须得人为地为其实现计算规则。

为此,由于最小存储单位为 ,这里以 位运算 的角度来分析一下上述式子进行计算的过程,首先是 A = 10 ,从 二进制 角度来看,其值显然为 A = 1010 ;而 B = 1 。对 AB 做求和运算,即 A + B 实际上也就是:

image-20220520161141583

对于 Σ = A + B = 1011 的结果简单说来就是,低位对齐,各位作和 ,由于并没有满足进位,再来看存在进位的例子 A + C ,也就是

image-20220520161155808

此时,还是先 低位对齐 ,然后进行 各位作和 运算,设进位标识符为 F

image-20220520161230315

通过对上述部分的分析,不难看出和 Σn 位数的值符合以下的规则:

image-20220520161244739

总结来说可以看作当且仅当 (A[n] + C[n] + F) % 2 = 1 时候 Σ[n] = 1 ,而 (A[n] + C[n] + F) % 2 = 0 时候 Σ[n] = 0

因此可以简化为

image-20220520161258020

至于关于 F 的值,若设 pi[n] 为变量 in 位计算前的初值,且 pFF 当前的值,也不难看出,当有 2 个数值参与运算时(两个数的位数同长)符合以下规则:

image-20220520161311079

显然,若 pF = 0 ,只有当 pA[n]pC[n] 都满足 pA[n] = pC[n] = 1 时,F = 1,而对 pF = 1 只要 pA[n] = 1pB[n] = 1 即可使得 F = 1

简而言之,可以写成

image-20220520161322191

如果其中一个数值(如设为 A)已算完,但此时 F = 1 ,需要对另一个数(如设为 C)进行补位,则满足以下规则:

image-20220520161335208

以及

image-20220520161348623

由于作简单的加算至多加到原数的 2 倍,因而以二进制来说,最终结果的 长度至多增加 1 位,也就是说,若设两个数 PQ ,则 P + Q 的和的二进制 最大长度为

image-20220520161357067

由此可知,如果由上述的规则将 Integer 类型进行加法运算,可以先将其转换为二进制,然后再进行 低位对齐,各位作和 ,同时根据进位标识符 F 进行补位,易知,在最差的情况下 时间复杂度

image-20220520161410866

这是什么概念呢,如果 PQ 当作十进制数来看,时间复杂度 相当于

image-20220520161427207

这么一看,效率还是比较可观的。

简单乘法

说到乘法,以小学的思维来看若取 R = P * Q ,则可以把看作 R 看作是 QP (或 PQ )相加的结果。这么看,怎么说呢,能用,但不完全够用(用吾等人师傅的话来说就是,所以其他人和其他人的使用者也就只能处在同一水平的圈子里了)。

假设以上面所述的方法来计算乘法,而再使用上一小节所述的加法实现法来对乘法进行实现,在不考虑效率,而只求结果的情况下,确实可行,但弊端也很明显——计算过程过于简单(搭积木水平)了。在最坏的情况下,无论所算的数的值是如何,若设

image-20220520161444179

在最坏情况下,时间复杂度 可以达到

image-20220520161456033

其中 β 为修正值,因为每次做加法运算都有可能出现进位的情况,而 MN 的值只与最大数值本身有关,这是很不好的结果。

那么,若以初中的思维来看一下有关数 R = P * Q 的计算过程,众所周知,乘法是符合 结合律分配律 的,不妨先以 结合律 的思想来做一个简单讨论。

此时若设对任意正整数 K > 0 ,有 R = P * (K * Q/K) ,也可看作

image-20220520161510195

image-20220520161522045

还可看作

image-20220520165312119

image-20220520161544358

此时也就可以人为地对通过对 K 值的构造来找到特定的、能使得对 PQ 有利(或只对 PQ 有利,或相比直接计算更效率)的情况。

但是,由于 PQ 都同为大整数,而上述式子所述的 K 值显然得满足为 Q 的非平凡因子,否则得到的结果会出现浮点数或无意义;同时,即便是找到了对应的 K 值,在计算 K/Q 时仍需要解决另一大与乘法类似的问题——除法(若将除法看作是乘倒数),这有点就像是进入了一个递归;并且若以上述方式作为分解,并不一定能够降低过程中进行加法运算的数量,甚至可能会比直接计算更多。

当然,可能对 结合律 应该也是有解的,就是说吾等人才疏学浅,就先不拓展了。

若再以 分配律 进行讨论,不妨将 R = P * Q 中的 Q 表示为 Q = K1 + K2 + K3 ... + Kn ,则原式有

image-20220520161624604

再次进行分解还可以看作是

image-20220520161635746

如果就此来看,似乎是比 结合律 更复杂了,且加法运算并没有得到改善。但是其中的 K1 K2 K3 ... Kn 如果从搞安全的角度看来,可以说成是 ”部分完全可控“(存在一种构造序列使得在部分个体满足一定条件时,其他部分完全可控) 的,既然是 ”部分完全可控“ 的,不妨以二进制的思想再来进行考虑。

显而易见,任何该 Integer 类型值集内数值(若计算结果为非负整数)都是可以使用二进制来表示,若对 Q 进行二进制分解,可得

image-20220520161647506

其中使得 m = n ,再将 Ci (i = 1,2,3, ... m ) 和 Ki (i = 1,2,3, ... n) 进行切合,带入上式,可得

image-20220520161706252

再进行简化成

image-20220520161732944

此时不妨将 R 看作一个 复合函数 ,如设

image-20220520161748738

其中 P 为非负整数,Cii = 1,2,3, ... m 的给定序列。

现在先对 m 值进行分析,由于这个 Ci 序列由 Q 分解得到,若以集合 S 来表示 Ci ,则

image-20220520161802188

即,求集合 S 的值只需要对 Q 进行移位运算(如向右移动 j 位),若其第 1 位值为 1 则称 (2^Cj) 为构成 Q 的一部分。显然移位运算和与运算属于 位运算 ,是很效率的。其次,由于 Q 在一般情况下二进制表示是存在 0 的,也就是说,对 m 的取值,有

image-20220520161813539

其中 |S| 为集合 S 的元素数量,这样就使得在计算总和时进行加法运算的数量有可能得以减少。再次,对于 Ci 序列,不难看出总有 Ca < Cb 当且仅当 a < b ,这就意味着若从 Q 的最高位开始求集合 S ,所得到的结果是 有序 的(降序),而对于以二进制表示的计算形如 (2^Ci)*P 实际上可以看作是 P 的二进制表示向左移动 Ci 位;若结合 有序 集合 S ,那么设

image-20220520161833235

则后一个结果 Ca 就能由前一个结果 Cb 通过向右移动 b - a 位得到。即对集合 S 内的所有

image-20220520161845423

只需在通过 P 由高到低移位得到第一个(设为 Cb)结果后,其直接后继的值(设为 Ca)可通过其直接前驱 Cb 移动 b - a 位得到,在最坏情况下,构造该集合 S时间复杂度

image-20220520161856659

同时,在 复合函数 R(Ci,P) 中,若将其看成一个多项式,则每一个 Ci 都对应一个子式

image-20220520161907287

则在求该函数的值时在最后会对这些子项进行一个求和,求和的数量为 m

再对每一个子式进行分析,显而易见,对任一

image-20220520161918812

进行求和时,若代入上一小结所述的方法,则该对子项加法运算时,在最坏的情况下,计算这对子项和的 时间复杂度

image-20220520161928672

其实就是会多计算 CaCb的值,因为在集合 S 中无相同的值,即 Ca != Cb ,因此在进行加法运算时,按照 低位对齐,各位作和 的规则,最坏的情况是指计算过程进 1 位的情况,此时所进行计算的 长度就为 Max{Ca,Cb} + bit(P) + 1

那么由此可以得出,若在最坏的情况下,整个乘法运算所需要的 时间复杂度 约为

image-20220520161948079

image-20220520162002284

即主要还是和 Q 有关,且主要影响的是在集合 S 的构成部分。如果使用该方法,实际运用时可以考虑分解较小的乘数。

幂次乘法

相较于简单加法和简单乘法,对幂次乘法来说,更像是在简单乘法的基础上再做乘法。不妨还是先以小学的角度来看有关幂次乘法的计算,如给定一个 R = P^Q 自然而然地想到,相当于 QP (或 PQ)进行相乘得到的结果。而乘法运算在如此角度来看,原型为多个数值的累加,以此再进行分解,将第 iP 自乘得到的结果记为 L{i} ,则可以得到递推式

image-20220520162013259

image-20220520162026965

若以这种思想进行计算,每一趟乘法都需要做 P 次的加法运算,设 U{i}{j} 为在做第 j 次加法运算时第 j-1 次得到的和,在最坏的情况下,第 i 趟乘法所作的加法运算的 时间复杂度

image-20220520162058866

由于对第 i 趟乘法中 L{i} 的每一次加法运算不可能每一次都会进位,所以 ɑ 仅作为一个修正值看待。

不难得出总的 时间复杂度

image-20220520162112671

image-20220520162124801

不妨先对 bit(L{i}) 进行分析,由于对任意

image-20220520162145317

显然总有

image-20220520162155974

而对任意 bit(L{i}) 存在

image-20220520162211462

若以最坏情况来看,即对每一个 bit(L{i+1}) = bit(L{i}) + bit(P) ,这就类似于等差数列求和了,时间复杂度 还可表示为

image-20220520162227962

其中,再将对第 i 趟乘法求和过程进行适当简化,不妨设 M[i] 为第 i 趟求和过程中对 的操作数,可由

image-20220520162238938

image-20220520162256519

易知

image-20220520162320627

那么

image-20220520162333677

整理可得

image-20220520162348263

image-20220520162358165

可见,如果直接按加法进行运算,在最坏的情况下,其 时间复杂度 是很大的,且受 影响不如值本身大,这对以二进制表示法来进行计算是很糟糕的。

若以上一小节所述的乘法来进行运算,则可以设第 iP 自乘得到的结果记为 F{i} ,得到递推式

image-20220520162410473

做一下简单的代入,很容易得到 时间复杂度

image-20220520162425594

image-20220520162440777

显然,后者为较佳的选择,不妨再对后者进行讨论。

由上面已知,对于 bit(F{i+1}) 最坏情况下为 bit(F{i+1}) = bit(F{i}) + bit(P) ,那么在以后者为前提,最坏情况下,还可以写成

image-20220520162453627

化简可得

image-20220520162509388

由此可见,起决定性作用的关键还是在 Q 上,因此若想加快幂次乘法的效率,就得从 Q 的优化入手。


应用

求幂算法

由上一章已经得出,若想对幂次乘法的计算做优化,就必须优化 Q ,而 Q 实际上在上一章的定义中为递推式的长度,也可以称为连乘的次数。

不妨先设 E 为求 R = P^Q 时所作的乘法数量,则此时根据前面所述的内容,可知 E = Q,用伪代码可以做以下表示

1
2
3
4
5
6
7
8
Integer pow(Integer P, Integer Q){
if(P == 0) return 0;
Integer R = 1;
for([1..Q]){
R = R * P;
}
return R;
}

显然这是比较通俗易懂的思想,但并没有能对 E 做到优化,可以以此为基础继续向下讨论。

首先,不难注意到 Q 作为幂次也是属于非负整数值集,且对于幂次的运算由于底数 P 相同,也就可以看作是对总幂次 Q 的加法链分解。当然最小加法链属于 NP完全问题 ,可求但代价有些大,不如用其他类似的、效果近似的方式使得让 E 尽可能的小于 Q ,这样就将幂次多连乘的问题分解成了求 Q 的次优加法链的问题。

现在来讨论第一种方案,对 Q 的值做一下分解

image-20220520162525845

其中对任意

image-20220520162537830

若设 R{i} 为第 i 趟乘法得到的值,则确保了

image-20220520162548894

即对当前所求的结果,总能从对前一个结果做平方得到。同时,为确保连续性,K1 的值必须为 1 ,用以表示 P 的初值。在最理想的情况下,也就是恰好存在这样一个关于 K 的序列,则做的乘数 E 恰好就为 bit(Q)

但并非所有数都能分解成这样的理想 K 序列,最简单的例子,如

image-20220520162603571

不难看出,在对 12 分解过程中,存在后一个 Kj ≠ 2*Ki 的情况,为此,就不能够简单的将这一步骤的结果以上一步结果的平方来表示了。

如果对 K 序列的理想值进行分析,显然可以看作是一个包含 1 的非负偶数集,即当存在 Kj ≠ 2*Ki 情况时,Kj 必然是非负偶数集的补集, Kj 为一个正奇数。应对这类情况的正确做法是,若当前期望得到的 Kj 值为奇数时,而此时上一步得到的 2*Ki 与期望值得到的 Kj 不符时,需要 2*Ki 补 “1” ,也就是将上一步结果与 P 做乘法运算,以弥补差值。

这样也就可以得到关于新的 K 的递归式

image-20220520162616718

还可以得到关于 R{i} 的递推式

image-20220520162630076

根据上述递推式,可写出以下递归函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Integer pow(Integer P, Integer Q){

if(Q == 0) return 1;
if(Q == 1) return P;

Integer R = pow(P,Q >> 1);

R = R * R;
if(Q % 2 == 1){
R = R * P;
}

return R;
}

其中递归段 Q >> 1 相当于 Q / 2 (向下取整),根据当前分解得到的的 K 值是否为奇数决定在最后是否再将上一步骤的结果乘上 P (补 “1”) 。

显然,该算法需要的 空间复杂度 为递归最大层数

image-20220520162645440

若将做乘法运算的次数 E 看作 时间复杂度 的计算单位,则 时间复杂度

image-20220520162657684

其中, CK 序列中奇数的数量。

若再对该算法进行讨论,易知,这是一个非尾递归函数,而一般来说,这类递归函数是可以用通过栈来模拟等价成非递归的递推形式。但如果使用栈来进行模拟意义不大,显然栈的深度和该算法递归时的 空间复杂度 一致,这样其 空间复杂度 并没有得到改善。

那么不妨对栈内所需存储的数据内容进行分析,由于每次调用内层递归时,Q 的值都会时原来的二分之一,即可看作向右移动 1 位,而判断是否为奇数看的是当前层 Q 二进制表示的第 1 位是否为 1 。也就是说,若忽略对当 Q 为奇数时的处理,则该算法可以作为尾递归来看待,此时,栈的作用就很明显了,是用以记录当前层 Q 的值是否为奇数的判断,以便在结束内层递归进行子问题组合时决定当前层是否乘上 P (补 “1”)。

实际上,若设 i 为算法的第 i 层递归调用(若将首次调用看作是第 1 层),则将当前层 Q的值即可看作是 Ki ,且满足

image-20220520162713831

此时也就可以通过将 Q 通过向右移位 i 层来获取当前层的 Ki 值,可写出以下递推函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Integer pow2(Integer P, Integer Q){

if(Q == 0) return 1;

Integer len = 0;
Integer R = P;

for(Integer i = Q; i > 0; len ++,i = i >> 1);
for(len = len - 2; len >= 0; len --){
R = R * ((Q >> len)&1 ? R * P : R);
}

return R;
}

在这个算法中多了一个 len 变量,用以记录 Q 值二进制表示的 的长度,然后通过对Qlen 的相关计算来模拟上述递归算法中第 len - 1 层递归的情况,以便决定是否乘上 P (补 “1”)。

总的来说相比递归算法其 空间复杂度 降低到了

image-20220520162727419

但相对的,需要知道 Q 值二进制表示的 的长度,多了一层计算,则一般 时间按复杂度

image-20220520162738882

实际上,还可以通过位运算来规避求层数的问题,如以下函数

1
2
3
4
5
6
7
8
9
10
11
12
Integer pow3(Integer P, Integer Q){

if(Q == 0) return 1;

Integer R = P;

for(Integer i = Q >> 1; i > 0; i = i >> 1){
R = R * ((Q^i)>Q ? R : P * R);
}

return R;
}

这样可进一步降低 时间复杂度

image-20220604210150922

不过,这对乘法运算的次数 E 并没有影响。

若设 C 为序列 K 中奇数的数量,显然有 C ≤ bit(Q),不妨取 C = bit(Q)/2 ,则乘法运算的次数 E 可表示为

image-20220520162754406

即在对幂次为 Q 的求幂算法中,只需要做 E 次乘法,这相较于直接做连乘是有很大改进的。

猜想

在上一小节中,是将 Q 分解成了关于 2*Kn 的递归式,这样总可以找到

image-20220520162804520

即在 K 序列中,任何值不相等且是 有序 的,若设 KiKj 的直接前驱,当知道了 Ki 的值,通过很简单的计算就能得到 Kj 的值。

但从另一个角度来看,由于 Q 是属于非负整数值集,如果设 [*] 为向下取整符号,则将其分解成

image-20220520162816042

也就是说若能确定一个 C 的值使得该等式成立,所需要的乘法运算次数就能降低至

image-20220520162827997

那么解决该问题的关键是如何求 C 值,并且 C 值最好能由 Q 或在求 P^(2^[log2(Q)]) 的过程中通过简单的计算得到,但似乎不太可能。


实现

链串法

由于C语言每次申请动态变量只能以"字节"为单位,无法精确到"位",为节省空间,不妨借鉴 链块串 的结构,根据 长来申请尽量少的字节,并用一个记录当前位数的变量来约束大整数的运算长度。

易知,一个字节等于 8 ,所以若设 [*] 为向上取整符号,且 size 为字节长度, bits 长,那么满足以下关系

image-20220520163045701

接着来讨论如何对某个字节的指定 进行操作,若设需要操作的位为第 n 个字节的第 i 位,且 n{i} 为第 n 字节的第 i 位(后文皆同)。当期望该 i 位的值为 0 时,需要将第 n 个字节和一个值为 2^i 的修正字节 m 的取反做与运算,即构造除第 i 位为 0 其他位全为 1 的字节;而当期望该 i 位的值为 1 时,则需要将第 n 个字节和一个值恰好为 2^i 的修正字节 m 做或运算,保证除了第 i 位为 1 外,其他位都为 0

至于修正字节 m 可以由 0x80 向右移动 8-i1 向左移动 i 位得到,以第二种方式为例,可得

image-20220520162858907

然后是关于存储的格式,为方便当作加法运算时能够很快的做到 低位对齐 ,设可以由低位开始,有序存储到 n = 0,1,2, ... size 的字节上。通俗地说,若将这些存储的字节看作数组,则相当于将数值二进制位从低到高,存到字节数组的从左到右(若设最左的下标号为 0 ,往右升序增 1) ,这样在做加法运算时,仅需让两个数的字节数组从下标为 0 的开始遍历计算即可。

但在做乘法运算时是需要进行数值二进制向左移动数位,若以这样的方式进行存储,在进行左移位运算时,就必须将字节数组中的所有值相对的往右移位。由于对字节数组变量扩容时,只能是往下标大的方向,无法在字节数组的左边补 0 ,因此需要将内容整体先向右移动,然后在其前面补上 0 。并且在推出下一个分解乘数时(即需要做右移位运算),还需将整个内容向左移动,显然是很不效率的。

为解决这种情况,可在做乘法运算时,将存储方式反过来,即将低位放到字节数组下标最高处,这样扩容时可以直接在更高的下标处补 0 ,而在推出下一个分解乘数时,只需改变表示总位的长度。

除此之外,还得考虑一些情况,如两数相加或相乘若其中一数为 0 则无需继续计算,返回另一数或 0 等等。

按照上述讨论,可使用C类语言写出对应代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
// 大整数计算
#define INTEGER_DEFAULT_SIZE 10

class Integer{

private:

typedef unsigned char byte;
int size;
int bits;
byte *pointer;

// 返回最高位所在的字节下标
int len(){
return (this->bits >> 3) + (this->bits%8 > 0);
}

// 判断字节数组是否为有效
bool null(){
return this->pointer == NULL;
}

// 判断是否为空值
bool empty(){
return null() || this->size == 0 || this->bits == 0;
}

// 判断第p位的值是否为 "1"
bool bit(int p){
if(p < 0 || p >= this->size) return false;
return (this->pointer[p >> 3] >> (7 - p % 8))&1;
}

// 扩容
void expand(){
int newSize = this->size > 1024 ? this->size + 1024 : this->size * 2;
int newLen = (newSize >> 3) + 1;
this->pointer = (byte*)realloc(this->pointer,sizeof(byte)*newSize);
for(register int i = len(); i < newLen; i++){
this->pointer[i] = 0;
}
this->size = newSize;
}

// 复制
void copy(const Integer &i){
this->size = i.size;
this->bits = i.bits;
if(i.size <= 0 || i.bits <= 0){
this->pointer = NULL;
return;
}
this->pointer = (byte*)calloc(this->size,sizeof(byte));
for(register int t = 0; t < len(); t++){
this->pointer[t] = i.pointer[t];
}
}

public:

Integer(){
this->size = INTEGER_DEFAULT_SIZE;
this->bits = 0;
this->pointer = (byte*)calloc(this->size,sizeof(byte));
}
Integer(bool empty){
this->size = 0;
this->bits = 0;
this->pointer = NULL;
}
Integer(int size){
this->bits = 0;
if(size <= 0){
this->size = 0;
this->pointer = NULL;
return;
}
this->pointer = (byte*)calloc(size,sizeof(byte));
this->size = size;
}
Integer(const Integer &i){
copy(i);
}
~Integer(){
if(!null()){
free(this->pointer);
this->size = 0;
this->bits = 0;
this->pointer = NULL;
}
}
// 设为 "0" 或归 "0"
void zero(bool del){
if(del){
this->~Integer();
this->size = INTEGER_DEFAULT_SIZE;
this->bits = 1;
this->pointer = (byte*)calloc(this->size,sizeof(byte));
}else{
this->bits = 0;
}
}
// 获取两数位最大长度
int maxBits(const Integer i){
return this->bits > i.bits ? this->bits : i.bits;
}
// 长整数类型转换(64bits)
void dex2i(long long int i){
int cur = 0;
byte st = 0x80;
for(register int tu = 0; i > 0; tu++){
for(register int tp = 0; tp < 8 && i > 0; tp++){
this->pointer[tu] = i&1 ? this->pointer[tu] | (st >> tp) : this->pointer[tu] & (~(st >> tp));
cur ++;
i >>= 1;
while(cur > this->size){
expand();
}
}
}
this->bits = cur;
}

// 转换为二进制串
char *bin(){

if(empty()) return NULL;

int tl = len();
int c = this->bits;
byte st = 0x80;
char *s = (char*)calloc(c + 1,sizeof(char));
s[c] = '\0';
for(register int tu = 0; tu < tl && c >= 0; tu++){
for(register int tp = 0, tv = 7; tp < 8 && c >= 0; tp++, tv--){
s[--c] = ((this->pointer[tu] & (st >> tp))>>tv) + '0';
}
}
return s;
}
// 等于
Integer &operator=(Integer i){
this->~Integer();
copy(i);
return *this;
}
// 加法运算
Integer operator+(Integer i){

if(empty() || i.empty()){
Integer it(empty() ? i : *this);
return it;
}

Integer it(maxBits(i) + 1);

bool flag = false;
bool a,b;
int itl = it.len();
int tl = this->len();
int il = i.len();
register int tu;
register int iu,ip,iv;
register int itp,itv,itu;
register int c = 0;

// 采用关于修正字节的右移方式进行位运算
byte st = 0x80;

// 初始化第一个加数
for(tu = 0; tu < tl; tu++){
it.pointer[tu] = this->pointer[tu];
}

// 加上第二个加数
for(iu = 0; iu < il; iu++){
for(ip = 0, iv = 7; ip < 8 && c < i.bits; ip ++, iv--){
a = (it.pointer[iu] >> iv) & 1;
b = (i.pointer[iu] >> iv) & 1;
it.pointer[iu] = (flag+a+b)&1 ? it.pointer[iu] | (st >> ip) : it.pointer[iu] & (~(st >> ip));
flag = (flag && (a || b)) || (a && b);
c++;
}
}

// 若存在局部进位
if(flag){
itp = c % 8;
itv = 7 - itp;
itu = c >> 3;
while(flag){
while(itp < 8 && flag){
a = (it.pointer[itu] >> itv) & 1;
it.pointer[itu] = (flag+a)&1 ? it.pointer[itu] | (st >> itp) : it.pointer[itu] & (~(st >> itp));
flag = (flag && a) || a;
itp ++;
itv --;
}
itp = 0;
itv = 7;
itu ++;
}
}

// 若存在整体进位
it.bits = it.bit(it.size - 1) ? it.size : it.size - 1;

return it;
}
// 乘法运算
Integer operator*(Integer i){

if(empty() || i.empty()){
Integer it;
it.zero(true);
return it;
}

Integer it(this->bits + i.bits);
Integer t(this->bits + i.bits);

// 优先分解较小的乘数
Integer *less,*more;

if(this->bits < i.bits){
less = this;
more = &i;
}else{
less = &i;
more = this;
}

bool a,b;
bool flag;
int tl = more->len();
register int im = less->bits - 1;
register int itp,itv,itu;
register int tp,tv,tu;
register int ip,iv,iu;
register int tc;

// 采用关于修正字节的左移方式进行位运算
byte st = 1;

// 高下标存储低位
itp = (more->bits + 8 - 1) % 8;
itu = more->len()-1;
itv = 7 - itp;

tp = 0;
tv = 7;
tu = 0;
tc = 0;

while(tu < tl){

while(tp < 8 && tc < more->bits){

if(itp < 0){
itu--;
itp = 7,itv = 0;
}

it.pointer[itu] = ((more->pointer[tu] >> tv) & 1) ? it.pointer[itu] | (st<<itv) : it.pointer[itu] & (~(st<<itv));
tc++;
itv++,tv --;
itp--,tp ++;
}
tp = 0;
tv = 7;
tu++;
}
it.bits = tc + im;

// 分解
while(im >= 0){

if(less->bit(im)){

flag = false;

iu = it.len() - 1;
ip = (it.bits + 8 - 1) % 8;
iv = 7 - ip;

tu = 0;
tp = 0;
tv = 7;

// 对分配律各项做和
while(iu >= 0){
while(ip >= 0){
if(tp >> 3){
tu ++;
tp = 0;
tv = 7;
}
a = (it.pointer[iu] >> iv) & 1;
b = (t.pointer[tu] >> tv) & 1;;
t.pointer[tu] = (flag+a+b)&1 ? t.pointer[tu] | (st<<tv) : t.pointer[tu] & (~(st<<tv));
flag = (flag && (a || b)) || (a && b);
ip--,iv++;
tp++,tv--;
}
ip = 7;
iv = 0;
iu --;
}

// 若存在局部进位
while(flag){
while(tp < 8 && flag){
a = (t.pointer[tu] >> tv) & 1;
t.pointer[tu] = (flag+a)&1 ? t.pointer[tu] | (st<<tv) : t.pointer[tu] & (~(st<<tv));
flag = (flag && a) || a;
tp ++;
tv --;
}
tp = 0;
tv = 7;
tu ++;
}

}
im--;
it.bits--;
}

// 若存在整体进位
t.bits = t.bit(t.size - 1) ? t.size : t.size - 1;

return t;
}
};

理论上使用该链串法可以极大节省存储空间,即对于一个非负整数 P 而言,若设 [*] 为向上取整符号,S(*) 为对应类型的长度,则用该方法需要的字节数组空间为

image-20220520163117851

所占的 空间大小还是比较接近 log2(P)

字节法

在上一小节的链串法中通过修正字节 m 和对应字节的 n 运算来对第 i 个位进行运算,虽然仅仅是位运算级别的移位运算,但当数足够大时造成的效率损失仍然是有的。如在做 P + Q 运算时,若设 C 为两数在进行位运算时修正字节 m 的移位总数量,在最坏的情况下,即存在进位的情况下,且每个字节数组都填满且都进行了对应位运算,容易得出

image-20220520163131009

而在字节法中以空间规避了这种多余的运算,直接在字节数组中用 1 个字节表示大数 1 个位。

用C类语言表示可得代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
// 大整数计算
#define DEFAULT_INTEGER_SIZE 100

class Integer{
private:

typedef unsigned char byte;
int size;
int len;
byte *pointer;

// 判断是否为空值
bool empty(){
return this->pointer == NULL || this->size == 0 || this->len == 0;
}

// 判断字节数组是否为有效
bool null(){
return this->pointer == NULL;
}

// 判断第n位的值是否为 "1"
bool bit(int n){
if(n < 0 || n >= this->size) return false;
return (bool)this->pointer[n];
}

// 扩容
void expand(){
int newLen = this->size > 2048 ? this->size += 1024 : this->size * 2;
this->pointer = (byte*)realloc(this->pointer,sizeof(byte)*newLen);
for(register int i = this->len;i < newLen; i++){
this->pointer[i] = 0;
}
this->size = newLen;
}

// 复制
void copy(Integer i){
if(i.empty()){
this->pointer = NULL;
this->len = 0;
this->size = 0;
return;
}
this->size = i.size;
this->len = i.len;
this->pointer = (byte*)calloc(this->size,sizeof(byte));
for(register int t = 0;t<this->len;t++){
this->pointer[t] = i.pointer[t];
}
}

public:

Integer(bool empty){
this->len = 0;
this->size = 0;
this->pointer = NULL;
}
Integer(){
this->len = 0;
this->size = DEFAULT_INTEGER_SIZE;
this->pointer = (byte*)calloc(DEFAULT_INTEGER_SIZE,sizeof(byte));
}
Integer(int n){
this->len = 0;
if(n <= 0){
this->size = 0;
this->pointer = NULL;
}
this->pointer = (byte*)calloc(n,sizeof(byte));
this->size = n;
}
~Integer(){
if(null()){
free(this->pointer);
this->pointer = NULL;
this->size = 0;
this->len = 0;
}
}
// 长整数类型转换(64bits)
void dex2i(long long int i){

register int tu = 0;
while(i > 0){
while(tu > this->size)
expand();
this->pointer[tu] = i & 1;
tu++;
i >>= 1;
}
this->len = tu;
}
// 转换为二进制串
char *bin(){

if(empty()) return NULL;

register int tu = 0;
register int sp = this->len;
char *s = (char*)malloc(sizeof(char)*(sp+1));

s[sp--] = '\0';
while(sp >= 0){
s[sp] = this->pointer[tu] + '0';
tu++,sp--;
}

return s;
}
// 设为 "0" 或归 "0"
void zero(bool del){
if(del){
this->~Integer();
this->size = DEFAULT_INTEGER_SIZE;
this->len = 1;
this->pointer = (byte*)calloc(DEFAULT_INTEGER_SIZE,sizeof(byte));
}else{
this->len = 0;
}
}
// 获取两数位最大长度
int cmpMax(Integer i){
return this->len > i.len ? this->len : i.len;
}
// 等于
Integer &operator=(Integer i){
this->~Integer();
copy(i);
return *this;
}
// 加法运算
Integer operator+(Integer i){

if(empty() || i.empty()){
Integer it(empty() ? i : *this);
return it;
}

Integer it(cmpMax(i) + 1);

bool flag = false;
bool a,b;
int tl = this->len;
int il = i.len;
register int tu,iu;

// 初始化第一个加数
for(tu = 0; tu < tl; tu ++){
it.pointer[tu] = this->pointer[tu];
}

// 加上第二个加数
for(iu = 0; iu < il; iu ++){
a = it.pointer[iu];
b = i.pointer[iu];
it.pointer[iu] = (a+b+flag)&1;
flag = (flag && (a || b)) || (a && b);
}

// 若存在局部进位
while(flag){
a = it.pointer[iu];
it.pointer[iu] = a^flag;
flag = (flag && a) || a;
iu++;
}

// 若存在整体进位
it.len = it.pointer[it.size - 1] ? it.size : it.size - 1;

return it;
}
// 乘法运算
Integer operator*(Integer i){

if(empty() || i.empty()){
Integer it;
it.zero(true);
return it;
}

Integer it(this->len + i.len);
Integer t(this->len + i.len);

// 优先分解较小的乘数
Integer *less,*more;

if(this->len < i.len){
less = this;
more = &i;
}else{
less = &i;
more = this;
}

bool a,b;
bool flag;
int tl = more->len;
register int im = less->len - 1;
register int tu,itu;

// 高下标存储低位
tu = 0, itu = tl - 1;
while(tu < tl){
it.pointer[itu] = more->pointer[tu];
tu ++,itu --;
}
it.len = im + tl;

// 分解
while(im >= 0){
if(less->pointer[im]){

flag = false;

itu = it.len - 1;
tu = 0;

// 对分配律各项做和
while(itu >= 0){
a = it.pointer[itu];
b = t.pointer[tu];
t.pointer[tu] = (a+b+flag)&1;
flag = (flag && (a || b)) || (a && b);
itu--, tu++;
}

// 若存在局部进位
while(flag){
a = t.pointer[tu];
t.pointer[tu] = a^flag;
flag = (flag && a) || a;
tu++;
}

}
im --;
it.len --;
}

// 若存在整体进位
t.len = t.pointer[t.size - 1] ? t.size : t.size - 1;

return t;
}
};

相比于链串法,使用字节法明显代码看起来少了很多,但相对的所占用的存储空间也有所增大。对于一个非负整数 P ,若设[*] 为向上取整符号, S(*) 为对应类型的长度,可以表示为

image-20220520163147386

所占的 空间大小约为 8*log2(P)


测试

大整数加法

为检测这两个算法对大整数加法的计算效率,如可先分别生成长度为 1000 的大整数序列 AB,然后依次进行加法运算,最后比较所使用的总时间。

若设 i 为大整数序列 AB 的第 i 个大整数,则有

image-20220520163200343

测试伪代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void test(){

Integer A,B,C;
Time begin,end,Total = 0;

for([1..1000]){
A,B = Random();

{
begin = Now();
C = C + A + B;
end = Now();
}

A,B = zero();
Total = Total + (end - begin);
}

}

链串法

如图所示

image-20220520124944741

一共耗费了 174ms

字节法

如图所示

image-20220520125301404

一共耗费了 120ms

可见若使用字节法约比使用链串法快了约 30% ,这也就是字节对指定位的位运算多消耗的时间。但字节法占用空间约为链串法的 8 倍可以根据实际情况斟酌选择。

大整数乘法

接下来是有关乘法的分析,可以和对大整数加法类似,先生成对应的序列 AB 然后将加法运算换为乘法运算,但考虑到做累积可能会差异越来越大,故只计算序列 AB 的乘积的平均时间。

测试伪代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void test(){

Integer A,B,C;
Time begin,end,Total = 0;

for([1..1000]){
A,B = Random();

{
begin = Now();
C = A * B;
end = Now();
}

A,B = zero();
Total = Total + (end - begin);
}

Total = Total / 1000;

}

链串法

如图所示

image-20220520140807672

平均每次计算耗费 151ms

字节法

如图所示

image-20220520141527236

平均每次计算耗费 94ms

可见字节法相比链串法快了约 37% ,相比加法运算乘法运算的差距更为明显一些。

大整数乘幂

对于大整数幂乘的测试,显然若使用随机数来进行测试,幂乘的结果会极大的拉开差异,因此该测试打算分别计算 100 以内质数以及部分数的 12345 次方,然后根据计算的时间进行比对。

测试伪代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void test(){

Integer C;
Integer S = {100以内质数} ∪ {10,100,1000,10000}
Time begin,end;

for([i ∈ S]){

C = i;

{
begin = Now();
pow(C,12345);
end = Now();
}

C = zero();
print(end - begin);
}

}

同样的,再分别计算 100 以内合数的 12345 次方。

测试伪代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void test(){

Integer C;
Integer S = {100以内合数}
Time begin,end;

for([i ∈ S]){

C = i;

{
begin = Now();
pow(C,12345);
end = Now();
}

C = zero();
print(end - begin);
}

}

链串法

关于求质数幂次的的结果,如图所示

image-20220520143217093

关于求合数幂次的结果,如图所示

image-20220520151614324

image-20220520151708812

字节法

关于求质数幂次的的结果,如图所示

image-20220520144538232

关于求合数幂次的结果,如图所示

image-20220520145505709

image-20220520145536980

可见当计算的结果很大时,链串法由字节对指定位的多余运算造成的效率影响就很明显了。

由于链串法和字节法都使用上两节所述的求幂算法对求幂时乘法运算的数量进行了优化,且故影响时间的主要因素为基数的大小。同时,不难看出随着基数的增大,除了一些特殊的数,如恰好为 2 的多次方,或存在 2 的多次方的因子时计算的速度相较周围其他数要快一些外,在 100 以内的合数和质数计算时间的增量较为平均。

若能申请到位空间,就可以节省开辟多余空间的时间,还会更快一些。


附录

上述的两个方法都是基于 C++ 的类实现的,若单纯靠结构和对应的函数来实现会不会快一些呢,经过测试并没有很明显的差异,反而在测试结果中,有多数结果所用耗时比用类进行包装效率还慢一些。

以下是用结构和函数实现的字节法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
#define BYTE_C 1
#define INT_DEFAULT_SIZE 100
typedef unsigned char BYTE;

struct Int{
int size;
int len;
unsigned char *pointer;
};

// 判断是否位空
bool i_Empty(Int *t){
return t == NULL || t->pointer == NULL || t->len == 0 || t->size == 0;
}

// 清除
void i_Del(Int *t){
if(t->pointer != NULL){
free(t->pointer);
t->pointer = NULL;
t->len = t->size = 0;
}
}

// 设为 "0" 或归 "0"
void i_Zero(Int *t, bool del){
if(del){
i_Del(t);
t->pointer = (BYTE*)calloc(1,BYTE_C);
t->len = t->size = 1;
}else{
t->len = 0;
}
}

// 获取两数位最大长度
int i_Cmp(Int *a, Int *b){
return a->len > b->len ? a->len : b->len;
}

// 扩容
void i_Expand(Int *t){
int newLen = t->size > 2048 ? t->size += 1024 : t->size * 2;
t->pointer = (BYTE*)realloc(t->pointer,BYTE_C*newLen);
for(register int i = t->len;i < newLen; i++){
t->pointer[i] = 0;
}
t->size = newLen;
}

// 转换为二进制串
char *i_Bin(Int *t){

if(i_Empty(t)) return NULL;

register int tu = 0;
register int sp = t->len;
char *s = (char*)malloc(sizeof(char)*(sp+1));

s[sp--] = '\0';
while(sp >= 0){
s[sp] = t->pointer[tu] + '0';
tu++,sp--;
}

return s;
}

// 长整数类型转换(64bits)
void i_Dex2i(Int *t, long long int i){

register int tu = 0;
while(i > 0){
while(tu > t->size)
i_Expand(t);
t->pointer[tu] = i & 1;
tu++;
i >>= 1;
}
t->len = tu;
}

Int *i_Init(){
Int *i = (Int*)malloc(sizeof(Int));
i->len = 0;
i->size = INT_DEFAULT_SIZE;
i->pointer = (BYTE*)calloc(INT_DEFAULT_SIZE,BYTE_C);
return i;
}

Int *i_Init(int n){
Int *i = (Int*)malloc(sizeof(Int));
i->len = 0;
i->size = n;
i->pointer = (BYTE*)calloc(n,BYTE_C);
return i;
}

Int *i_Init(Int *c){
if(c == NULL) return NULL;
Int *i = (Int*)malloc(sizeof(Int));
i->len = c->len;
i->size = c->size;
i->pointer = (BYTE*)calloc(i->size,BYTE_C);
for(register int t = 0; t < i->len ; t++)
i->pointer[t] = c->pointer[t];
return i;
}

// 加法运算
Int *i_Add(Int *t, Int *i){

if(i_Empty(t) || i_Empty(i)){
Int *it = i_Init(i_Empty(t) ? i : t );
return it;
}

Int *it = i_Init(i_Cmp(t,i) + 1);

bool flag = false;
bool a,b;

int tl = t->len;
int il = i->len;

register int tu,iu;

for(tu = 0; tu < tl; tu++){
it->pointer[tu] = t->pointer[tu];
}

for(iu = 0; iu < il; iu++){
a = it->pointer[iu];
b = i->pointer[iu];
it->pointer[iu] = (a+b+flag) & 1;
flag = (flag && (a || b)) || (a && b);
}

while(flag){
a = it->pointer[iu];
it->pointer[iu] = a^flag;
flag = (flag && a) || a;
}

it->len = it->pointer[it->size - 1] ? it->size : it->size - 1;
return it;
}

// 乘法运算
Int *i_Multi(Int *p, Int *q){

if(i_Empty(p) || i_Empty(q)){
Int *it = i_Init();
i_Zero(it,true);
return it;
}

Int *it = i_Init(p->len + q->len);
Int *t = i_Init(p->len + q->len);

Int *ts, *i;
if(p->len < q->len){
ts = q;
i = p;
}else{
ts = p;
i = q;
}

bool a,b;
bool flag;

int tl = ts->len;
register int im = i->len - 1;
register int tu,itu;

tu = 0, itu = tl - 1;
while(tu < tl){
it->pointer[itu] = ts->pointer[tu];
tu ++,itu --;
}
it->len = im + tl;

while(im >= 0){
if(i->pointer[im]){
flag = false;

itu = it->len - 1;
tu = 0;
while(itu >= 0){
a = it->pointer[itu];
b = t->pointer[tu];
t->pointer[tu] = (a+b+flag)&1;
flag = (flag && (a || b)) || (a && b);
itu--, tu++;
}

while(flag){
a = t->pointer[tu];
t->pointer[tu] = a^flag;
flag = (flag && a) || a;
tu++;
}

}
im --;
it->len --;
}

t->len = t->pointer[t->size - 1] ? t->size : t->size - 1;
free(it);
return t;

}

后话

就是说,上述的所有内容,纯属个人无聊的臆想,没有用足够大的测试集测试过,仅能保证在测试章节中所有数据的正确。无法保证理论、其他未测试结果的正确性!然后,该滚去捣鼓合约了!


如果您喜欢此博客或发现它对您有用,则欢迎对此发表评论。也欢迎您共享此博客,以便更多人可以参与。如果博客中使用的图像侵犯了您的版权,请与作者联系以将其删除。谢谢 !