简介:
对于一些大的整数,由于计算机本身能够显示的内置数据类型精度有限,在处理一些比较大的整数运算时就不能适用。因此需要考虑用一些结构来辅助运算。一种典型的方式就是通过数组的方式来保存这些大整数。然后通过模拟手工运算的逐位运算。下面对整数的加法和乘法做一个总结。
加法:
位相加的关系:
笼统的来说,加法中数组的每一个元素都对应着整数的每一位。当两个数相加的时候,要把前面的进位和当前的和相加,然后根据结果来进行进位。如果仔细考虑的话,会发现有如下的情况存在:
假设有两个数组a[], b[], 和进位标志carryBit.
如果a[i] + b[i] + carryBit > 当前的数制,则carryBit要置位,相加的结果要减去当前的数制。
比如a[i] = 5, b[i] = 7, carryBit = 1。考虑10进制的情况。则相加的结果为13. 那么根据讨论,后面一位的进位标志为1, 当前的结果为13 - 10 = 3.
如果对上一步的讨论做进一步的提炼,我们会发现他们的运算实际上满足这么一个关系:
当前位的求和结果 = (a[i] + b[i] + carryBit) % 10,
下一位的进位标志(carryBit) = (a[i] + b[i] + carryBit) / 10
对于更加通用的数制运算,我们可以发现有同样对应的关系:
当前位的求和结果 = (a[i] + b[i] + carryBit) % 数制,
下一位的进位标志(carryBit) = (a[i] + b[i] + carryBit) / 数制。
数据的表示:
在前面的逻辑关系理请之后,剩下的就是如何保存对应的数据了。一般我们展示的数字比如:12345,一般都是高位在前面,低位在后面。而在进行数组的加法运算的时候,需要从低位到高位,那么在数组中的保存方式比较合理的方式应该为int[] a = {5, 4, 3, 2, 1}.这样,当两个数组相加的时候,我们只要从数组的开头遍历就可以了。同时,因为我们保存数据的顺序和显示数据的顺序是相反的,如果后续需要显示对应的数字的话,则需要倒序输出。
另外,两个数字相加之后,保存相加结果的数组长度必须要加1,这样才能保证有足够的空间将结果保存下来。
实现:
考虑一种最简单的情况,假设两个数组的长度相同。有了前面的讨论,我们就可以很容易实现如下的方法:
public static int[] genericPlus(int[] a, int[] b, int numberSystem) { int[] c = new int[a.length + 1]; int carryBit = 0; for(int i = 0; i < a.length; i++) { c[i] = (a[i] + b[i] + carryBit) % numberSystem; carryBit = (a[i] + b[i] + carryBit) / numberSystem; } c[a.length] = carryBit; return c; }
当然,这是一种比较理想的情况。经过前面一些网友的指正,更通用的情况下还需要考虑两个数组长度不相同的情况。那么,一个详细的实现方法如下:
public static int[] comparePlus(int[] a, int[] b, int numberSystem) { if(a.length == b.length) { // Common routine int[] c = new int[a.length + 1]; int carryBit = 0; for(int i = 0; i < a.length; i++) { c[i] = (a[i] + b[i] + carryBit) % numberSystem; carryBit = (a[i] + b[i] + carryBit) / numberSystem; } c[a.length] = carryBit; return c; } else if(a.length > b.length) { // Routine 1 int[] c = new int[a.length + 1]; int carryBit = 0; int i; for(i = 0; i < b.length; i++) { c[i] = (a[i] + b[i] + carryBit) % numberSystem; carryBit = (a[i] + b[i] + carryBit) / numberSystem; } while(i < a.length) { c[i] = (a[i] + carryBit) % numberSystem; carryBit = (a[i] + carryBit) / numberSystem; } c[a.length] = carryBit; return c; } else { // Routine 2 } }
这个部分的代码总的思路就是先判断两个数组的长度是否相同,如果相同则分配一个长度+1的数组,然后遍历数组,并将结果返回。在一个数组长度比另外一个大的情况下,则需要先遍历完短数组的那一段。剩下的部分遍历时则运算的结果变为:c[i] = (a[i] + carryBit) % numberSystem; carryBit = (a[i] + carryBit) / numberSystem;(这里假设a是长的那个)。剩下的那部分也可以照此类推。这里将三个条件的处理都放在一个方法里面了。实际代码里可以分别定义不同的方法来实现。
乘法:
有了前面加法讨论的基础,再考虑乘法则相对方便一些了。我们在考虑一下原来乘法的思路。对于两个数组a[], b[],假定结果数组为c[]。我们对数组相乘的步骤一般如下:
1. 取b[]中的一个元素,和a[]相乘,得到一个a.length + 1长度的中间数组。
经过遍历b[],我们就得到b.length长度这么多个中间数组。
2. 对于这些中间数组,如果对应的是b[i]乘积的结果,则后面求和的时候将这个数组左移i位,然后和总结果数组c[]相加。
这样得到的结果就是乘积。对于两个数组相乘,其结果的长度为两个数组长度之和。
实现:
经过前面的分析,我们可以得到如下的代码:
public static int[] arrayMultiply(int[] a, int[] b) { int[] c = new int[a.length + b.length]; for(int i = 0; i < b.length; i++) { // Generate a multiply result from b[i] * a int[] middleResult = new int[a.length + 1]; int carryBit = 0; for(int j = 0; j < a.length; j++) { middleResult[j] = (b[i] * a[j] + carryBit) % 10; carryBit = (b[i] * a[j] + carryBit) / 10; } middleResult[a.length] = carryBit; // Plus middle result to c carryBit = 0; for(int k = 0; k < middleResult.length; k++) { int sum = middleResult[k] + c[i + k] + carryBit; c[i + k] = sum % 10; carryBit = sum / 10; } } return c; }
注:前面这种实现只是针对10进制的方式。如果需要换成更加通用的方式,可以将10换成传进来的进制参数。当然函数签名也要做相应的修改。
另外,这种写法只是一个比较粗略的写法,从可读性的角度来说完全可以将生成中间结果数组和将中间结果数组加到最终结果数组的两部分分成两个方法。
数据展示的问题:
前面保存数据的时候是采用数组的方式,而且存储的方式和我们显示的方向是相反的。经过前面网友的提醒,在展示数据的时候,可能会存在一个问题。就是如果两个数相加的时候,并不一定会进位。前面的运算结果是直接分配了增加一个长度位的数组。当没有进位的时候,保存在最高位的数字是0. 因此,一种办法是在展示数字的时候,判断一下最高位来跳过这个0.
比如我们一个输出数组元素的方法,其实现则应该如下:
public static void printBinaryArrays(int[] array) { if(array[array.length - 1] == 0) { for(int i = array.length - 2; i >= 0; i--) System.out.print(array[i]); } else { for(int i = array.length -1; i >= 0; i--) System.out.print(array[i]); } System.out.println(); }
总结:
这里主要讨论了大整数的加法和乘法,对于减法来说,思路也很近似,相信看过这个之后大家也该知道怎么做了。当然,这种大整数的运算在本文里的实现并不是可以无穷大。目前的一个实现是长度最多到Integer.MAX_VALUE,也就是2^31 -1这么多位的数字。如果需要更多位数的话,可能就需要Long数据类型甚至一些自定义的类型了。这种问题本身不是很难,只是如果要在很短的时间内理清思路并不出问题,确实还是有点挑战性。前面kissinger同学曾经在这个问题上栽了,在此聊表慰问一下吧:)。
补充:
一些相加和相乘的过程中,可能会出现的各种细节问题,比如长度限制,不同长度数据的运算等等。感谢前面一些网友的指正。
相关推荐
操作用二维数组表示,其中的每个操作用一个含有两个正整数 a 和 b 的数组表示,含义是将所有符合 0 <= i < a 以及 0 <= j < b 的元素 M[i][j] 的值都增加 1。 在执行给定的一系列操作后,你需要返回矩阵...
给定两个N × N的稀疏矩阵A和B,其中矩阵A有P个元素非0,矩阵B有Q个元素非0。请计算两个矩阵的乘积C = A × B并且输出C中所有非0的元素。 输入 第一行包含三个整数N, P, Q 以下P行每行三个整数i, j, k表示A矩阵的一...
2、用公式求和、求乘积-11 6 3、字符串字符数组-12 16 4、一维数组-3 27 5、二维数组-7 29 6、数的拆分-3 36 7、素数-2 38 8、最大公约数,最小公倍数-6 39 9、其他-1 44 《C语言程序设计》复习纲要 1、 考试题型...
1-50 动态规划 1005 打导弹 1006 乘积最大 1007 加分二叉树 1008 合唱队形 1017 最大0,1子矩阵 这题要想不超时,必须DP 1020 最大正方形 这题和1017很相似,不过有更...1001 整数求和 1026 求最值 1027 整数礼物
快臂 FastARM:为移动世界优化的库 什么是 FastARM? FastARM 是一个直接用 32 位 ARM 汇编编写的优化函数的集合...浮点向量求和,乘积 快速整数平方根 FAST RC4 实现,在 Raspberry Pi B 上产生超过 40MB/s 的速度。
阶乘:非负整数n的阶乘是所有小于或等于n的正整数的乘积。 找到5! 递归地斐波那契数列:斐波那契数列中的前两个数字是0和1,每个后续数字是前两个数字的和。 递归产生序列。 范围序列:递归地产生一个3到9且互斥的...
2.4.5 MULTINOMIAL——计算多个数字和的阶乘与各数字阶乘乘积的比值 86 2.4.6 MDETERM——计算数组的矩阵行列式的值 86 2.4.7 MINVERSE——计算数组的逆矩阵 87 2.4.8 MMULT——计算两个数组的矩阵乘积 88 ...
EXCEL中求两列的对应元素乘积之和 计算900~1000之间的数值之和 双条件求和 如何实现这样的条件求和 A1:A10数字显为文本格式时,如何求和 如何分班统计男女人数 统计数值大于等于80的单元格数目 计算出A1里有几个abc ...
EXCEL中求两列的对应元素乘积之和 计算900~1000之间的数值之和 双条件求和 如何实现这样的条件求和 A1:A10数字显为文本格式时,如何求和 如何分班统计男女人数 统计数值大于等于80的单元格数目 计算出A1里有几个abc ...
两个整数的和389. 找不同462. 最小移动到相等数组元素 II 258.加数字226. 反转二叉树451. 按频率排序字符260.单数III 492.构造矩形506.相对等级283. 移零530. BST 中的最小绝对差异529.扫雷167.Two Sum II - 输入...
其中求和在 i 上,乘积在 j 上,c_i 是多项式项系数的集合,x_ij 是一组符号变量,p_ij 是项中每个变量的(通常是正整数)指数,其中至少有一个 p_ij对于给定的 i 非零,k 是常数项。 sympoly 支持常规的元素和...
7.3 非负整数递归函数(Recursive Functions on Nonnegative Integers) 7.4 算术表达式(Arithmetic Expressions) 7.5 递归数据型在计算机科学中的简介(Induction in Computer Science) 8 无限集(Infinite Sets...
4、有一个分数序列:1/2,1/3,1/4,1/5,1/6,1/7,……,编写函数求序列前n项之和,要求在主程序中提示用户输入整数n,并判断所输入数是否合法(大于1为合法),如果合法则调用求和函数并输出结果。 5、计算两个日期之间...
实例058 乘积大于和的数 74 实例059 求各位数之和为5的数 75 第6章 数据输入与输出函数 77 实例060 使用字符函数输入/输出字符 78 实例061 输出相对的最小整数 79 实例062 将小写字母转换为大写字母 80 实例063 水池...
2、从卡号最后一位数字开始,逆向将偶数位数字,先乘以2(如果乘积为两位数,则将其减去9),再求和。 3、将奇数位总和加上偶数位总和,结果应该可以被10整除。 例如,卡号是:5432123456788881 则奇数、偶数位(用...
实例125 乘积大于和的数 188 实例126 求各位上和为5的数 189 实例127 计算某日是该年第几天 190 4.2 排序算法 191 实例128 直接插入排序 192 实例129 希尔排序 193 实例130 起泡排序 194 实例131 ...
姜尚仆 -《模线性方程的应用——用数论方法解决整数问题》 金 恺 -《探寻深度优先搜索中的优化技巧——从正方形剖分问题谈起》 雷环中 -《结果提交类问题》 林希德 -《求最大重复子串》 刘才良 -《平面图在信息...