当简单的计算遇上了大数,其实大数运算也很简单
t3138011
8年前
<h3><strong>一、说三道四</strong></h3> <p>用代码实现简单的加减乘除运算会不会?只要你是个coder,我想这个答案都是肯定的吧!</p> <p>但是,今天我想说的是,当我们的运算遇到了大数,用原本的int、long、float、double数值类型</p> <p>都无法表示出来的时候,你们想过该如果解决这一类型的问题了吗?</p> <p>在这,你们可以先不用看卤煮撸的代码,想想如果自己遇到这个问题,该如果解决,也许你的想法</p> <p>很新颖,思路以及在算法的实现上更清晰。希望能够在广大的博友的集思广益下,大数的运算能够有</p> <p>一套更好的解决方案。不说了,咱们先撸代码吧。毕竟这才是主题!!!</p> <h3><strong>二、大数运算之加法运算</strong></h3> <pre> <code class="language-java"> package com.linjm.work; public class Add { public String forAdd(String p, String q) { String x = p; String y = q; int len = 0; String res = ""; len = (x.length() > y.length()) ? x.length() : y.length(); if (len == x.length()) y = Tools.fillZero(y, x.length() - y.length()); if (len == y.length()) x = Tools.fillZero(x, y.length() - x.length()); x = Tools.reverse(x); y = Tools.reverse(y); //m,n用于循环遍历时截取字符串x,y的每一位 //flag用于标识m和n的每一次相加是否需要进位 int m, n, flag = 0; //遍历x、y,对应位相加 for (int i = 0; i < len; i++) { int sum; m = Integer.parseInt(x.substring(i, i + 1)); n = Integer.parseInt(y.substring(i, i + 1)); sum = m + n; if (flag == 1) { sum = sum + 1; flag = 0; } if (sum >= 10) { flag = 1; sum = sum - 10; } res += sum; } if (flag == 1) //最高位相加后还大于10,则须进位 res += "1"; return Tools.reverse(res); } public static void main(String[] args) { Add add = new Add(); System.out.println(add.forAdd("555555555555555555", "5555555555555555551")); } } 大数相加</code></pre> <p>思路分析:</p> <p>大数的相加主要是通过字符串的相加来实现的。两个大数相加,找出位数较大的那个大数获取对应的长度,</p> <p>然后对较小的那个数进行左补0直至长度和较大的那个数的位数一样,最后循环累加两个大数的每一位的数值,</p> <p>遇到需要进位的需要设一个标识位标识。</p> <h3><strong>三、大数运算之减法运算</strong></h3> <pre> <code class="language-java"> package com.linjm.work; public class Sub { public String forSub(String p, String q) { String x = p; String y = q; int len = 0; String res = ""; int sign = 0; //0: x >= y、1: x < y sign = Tools.forMax(x, y) ? 0 : 1; if (sign == 1) { x = q; y = p; } len = x.length(); y = Tools.fillZero(y, x.length() - y.length()); int m, n, flag = 0, num = 0; //num标识出现0的次数,防止结果中高位出现多个0的情况 for (int i = len; i > 0; i--) { int dif; m = Integer.parseInt(x.substring(i - 1, i)); n = Integer.parseInt(y.substring(i - 1, i)); dif = m - n; //标志位如果等于1,说明存在借位 if (flag == 1) { dif = dif - 1; flag = 0; //重置标志位 } //判断是否需要借位 if (dif < 0) { flag = 1; //标记 dif = dif + 10; } if (dif == 0) { num ++; } else { num = 0; } res += dif; } if (Tools.isZero(res)) return "0"; if (num > 0) { res = res.substring(0, res.length() - num); //截取掉高位出现的连续num个0 } return (sign == 1) ? "-" + Tools.reverse(res) : Tools.reverse(res); } public static void main(String[] args) { Sub sub = new Sub(); System.out.println(sub.forSub("100000000", "1")); } } 大数相减</code></pre> <p>思路分析:</p> <p>大数相减在实现上和大数相加异曲同工,也是通过循环遍历大数的每一位,对其进行数值相减,在遇到需要借位的数值,</p> <p>设立一个标识位进行标识。当遇到被减数比减数小的时候,先用减数减去被减数,用标识位标识被减数比减数小,最后结果</p> <p>根据标识变量判断是否需要在结果上加上"-"。</p> <h3><strong>四、大数运算之乘法运算</strong></h3> <pre> <code class="language-java"> package com.linjm.work; public class Mul { public String forMul(String p, String q) { String x = Tools.maxNum(p, q); String y = Tools.minNum(p, q); if (y.length() > 15) { return "ERROR:两位数中必须有一个数的长度要小于15"; } String sum = "0"; Add add = new Add(); Sub sub = new Sub(); while (Long.parseLong(y) > 0) { sum = add.forAdd(sum, x); y = sub.forSub(y, "1"); } return sum; } public static void main(String[] args) { Mul mul = new Mul(); System.out.println(mul.forMul("1000", "20000")); } } 大数相乘</code></pre> <p>思路分析:</p> <p>大数相乘在算法的实现上个人表示有点不太满意,虽然实现了功能,但还是觉得代码的实现上和思路都很挫。</p> <p>乘法的最终思路就是多个数值的加法运算。所以大数的乘法就是多个大数的加法运算。但是遇到两个数值都是大数的情况下,</p> <p>运行速度会非常的慢。</p> <h3><strong>五、大数运算之除法运算</strong></h3> <pre> <code class="language-java"> package com.linjm.work; public class Div { public String forDiv (String p, String q) { String x = p; String y = q; String res = "0"; String remain = "0"; //余数 if (!Tools.forMax(x, y)) { return x + "的值要大等于" + y; } Add add = new Add(); Sub sub = new Sub(); while (true) { x = sub.forSub(x, y); res = add.forAdd(res, "1"); if (!Tools.forMax(x, y)) { remain = x; break; } } if (!Tools.isZero(remain)) res = res + "……" +remain; return res; } public static void main(String[] args) { Div div = new Div(); System.out.println(div.forDiv("222222222222222222222", "222222222222222222221")); } } 大数相除</code></pre> <p>思路分析:</p> <p>除法运算的实质也就是减法,让被除数一直减去除数,直到减不动了为止,统计下减了多少次除数,这个值就是商咯。</p> <p>但是存在的问题还是和大数的乘法是一样的,有待优化。</p> <h3><strong>六、大数运算之工具类</strong></h3> <pre> <code class="language-java"> package com.linjm.work; public class Tools { /** * @param s num * @Desc 字符串左补num个0 * @return String * */ public static String fillZero(String s, int num) { String res = ""; for (int i = 0; i < num; i++) { res += "0"; } return res + s; } /** * @param s * @Desc 反转字符串 * @return String * */ public static String reverse(String s) { String res = ""; for (int i = s.length(); i > 0 ; i--) { res += s.substring(i - 1, i); } return res; } /** * @param x n(n最小值为1) * @Desc 获取字符串的n个字符 * @return int * */ public static int numAt(String x, int n) { return Integer.parseInt(x.substring(n - 1, n)); } /** * @param x y * @Desc 获取两个大数中较大的数 * 注:此方法不对两个数是否是数字进行校验 * @return String * */ public static String maxNum(String x, String y) { String max = ""; if (x.length() > y.length()) { max = x; } else if (x.length() == y.length()) { for (int i = 1; i <= x.length(); i++) { if (numAt(x, i) != numAt(y, i)) { max = (numAt(x, i) > numAt(y, i)) ? x : y; } else if (i == x.length()) { max = x; } } } else if (x.length() < y.length()) { max = y; } else { return "ERROR"; } return max; } /** * @param x y * @Desc 获取两个大数中较小的数 * 注:此方法不对两个数是否是数字进行校验 * @return String * */ public static String minNum(String x, String y) { String min = ""; if (x.length() > y.length()) { min = y; } else if (x.length() == y.length()) { for (int i = 1; i <= x.length(); i++) { if (numAt(x, i) != numAt(y, i)) { min = (numAt(x, i) > numAt(y, i)) ? y : x; } else if (i == x.length()) { min = x; } } } else if (x.length() < y.length()) { min = x; } else { return "ERROR"; } return min; } /** * @param x y * @Desc 大数x是否大于大数y * @return true/false * */ public static boolean forMax(String x, String y) { if (x.length() > y.length()) { return true; } else if (x.length() == y.length()) { for (int i = 1; i <= x.length(); i++) { if (numAt(x, i) != numAt(y, i)) { return (numAt(x, i) > numAt(y, i)) ? true : false; } else if (i == x.length()) { return true; } } } else if (x.length() < y.length()) { return false; } else { System.out.println("ERROR!!!"); } return false; } /** * @param x * @Desc 判断x是否是0或000…… * @return true/false * */ public static boolean isZero(String x) { boolean flag = true; for (int i = 1; i <= x.length(); i++) { if (Tools.numAt(x, i) != 0) { return false; } } return flag; } } 工具类</code></pre> <h3><strong>七、卤煮有话说</strong></h3> <p>算法的实现上可以会多多少少存在点瑕疵,第一遍写出来的代码不是最好的,但我们要尽我们所能去优化和改善我们的代码。</p> <p>大家有什么想法都可以说出来,我们一起来探讨大数的加减乘除,这样让这么有意义的事可以得到最后的解决方案。</p> <p>想是一回事,做又是另一回事。让我们脑洞大开,集思广益一起来探讨吧!!!</p> <p>如果你觉得博文写的不错,就点下【 推荐一下 】或【 打赏 】 卤煮一杯奶茶吧!!!</p> <p> </p> <p>来自:http://www.cnblogs.com/JimLy-BUG/p/5965487.html</p> <p> </p>