您的位置: 首页  >  文章  >  一个一百亿的计算器的实现

一个一百亿的计算器的实现

分类: 文章 • 2024-07-10 11:31:16

一个一百亿的计算器的实现

网上一搜一大把，搜出来的结果几乎都是我很崇敬的张孝祥老师写的这道题的思路，甚至有的直接把原文copy paste过来，没有一个用代码实现了的。于是自己琢磨了下，这里发布出来。虽然标题是一百亿，但实现结果可用于任意大整数。

原文地址  http://blog.****.net/wilsonpeng3/article/details/22441009

直接上代码。这里只实现了大整数相加。有了这个，不难实现减、乘等其他操作。代码复制粘帖即可运行。

MyBigInteger.java

[java] view plain copy
  1. import java.util.ArrayList;  
  2. import java.util.regex.Matcher;  
  3. import java.util.regex.Pattern;  
  4.   
  5. /** 
  6.  * Created by Rocky on 14-3-26. 
  7.  */  
  8. public class MyBigInteger {  
  9.     private char sign = '0';   // 0 表示正数  - 表示负数  
  10.     private byte[] data;  
  11.   
  12.     public MyBigInteger() {  
  13.         this.data = "0".getBytes();  
  14.     }  
  15.   
  16.     public MyBigInteger(String value) throws Exception {  
  17.         //正则表达式，输入字符串要求以 零个或一个 - 开头，其余都是数字  
  18.         Pattern pattern = Pattern.compile("^-?\\d+$");  
  19.   
  20.         if (value == null || value.length() <= 0) {  
  21.             value = "0";  
  22.         }  
  23.         Matcher matcher = pattern.matcher(value);  
  24.         if (!matcher.find()) {  
  25.             throw new Exception("the value is not a number string :" + value);  
  26.         }  
  27.         //获取字符串的第一个字符  
  28.         char firstChar = value.charAt(0);  
  29.   
  30.         //data应该保存的是第一个非0数字后的字符串  
  31.         if (firstChar == '-') {  //说明输入的是个负数  
  32.             if (value.length() >=2) {  
  33.                 sign = firstChar;  
  34.                 value = value.substring(1);  
  35.                 value = getTemp(value); //得到value中第一个非0后的子字符串。  
  36.             }  
  37.         } else {  
  38.             value = getTemp(value);  
  39.         }  
  40.         this.data = value.getBytes();  
  41.     }  
  42.   
  43.     /** 
  44.      * 得到一个字符串第一个非0后的字符串，如果没有找到，则返回 "0" 。如：00003435534，则返回3435534 
  45.      * @return 
  46.      */  
  47.     private String getTemp(String value){  
  48.         Pattern pattern = Pattern.compile("[^0]{1}");  
  49.         Matcher matcher = pattern.matcher(value);  
  50.         if (matcher.find()) {  
  51.             value = value.substring(matcher.start());  
  52.         } else {  
  53.             value = "0";  
  54.         }  
  55.         return value;  
  56.     }  
  57.   
  58.     public MyBigInteger add(MyBigInteger other) {  
  59.         MyBigInteger result = new MyBigInteger();  
  60.         int thisLength = this.data.length;  
  61.         int otherLength = other.data.length;  
  62.         int shorterLength = thisLength > otherLength ? otherLength : thisLength;  
  63.         ArrayList<Byte> resultData = new ArrayList<Byte>();  
  64.         int flag = 0;  //表示相加时的 进位，或相减时的 借位  
  65.         int i = thisLength - 1;  
  66.         int j = otherLength - 1;  
  67.         int k = shorterLength;  
  68.   
  69.         //两个数的符号相同  
  70.         if (other.sign == this.sign) {  
  71.             //从两个整数的个位开始依次相加  
  72.             while (k > 0) {  
  73.                 Integer temp = new Integer(new String(new byte[]{this.data[i]})) + new Integer(new String(new byte[]{other.data[j]})) + flag;  
  74.                 flag = temp / 10;  //相加结果超过10时的进位。没有超过10，进位为 0  
  75.                 resultData.add(0, ((temp % 10) + "").getBytes()[0]);  //把相加结果保存起来  
  76.                 k--;  
  77.                 i--;  
  78.                 j--;  
  79.             }  
  80.             //把多出的位加入到结果中  
  81.             if (i == -1) {  
  82.                 while (j >= 0) {  
  83.                     Integer temp = new Integer(new String(new byte[]{other.data[j]})) + flag;  
  84.                     flag = temp / 10;  
  85.                     resultData.add(0, ((temp % 10) + "").getBytes()[0]);  
  86.                     j--;  
  87.                 }  
  88.             } else if (j == -1) {  
  89.                 while (i >= 0) {  
  90.                     Integer temp = new Integer(new String(new byte[]{this.data[i]})) + flag;  
  91.                     flag = temp / 10;  
  92.                     resultData.add(0, ((temp % 10) + "").getBytes()[0]);  
  93.                     i--;  
  94.                 }  
  95.             }  
  96.             //最后把flag加进结果中  
  97.             if (flag != 0) {  
  98.                 for (byte by : (flag + "").getBytes()) {  
  99.                     resultData.add(0, by);  
  100.                 }  
  101.             }  
  102.             result.sign = other.sign;  
  103.         } else {  //符号不同  
  104.             if (thisLength > otherLength) {  //说明this表示的整数绝对值大，所以最终结果的符号为this的符号  
  105.                 result.sign = this.sign;  
  106.                 resultData = subtract(this.data, other.data);  //执行减法  
  107.             } else if (thisLength < otherLength) {  //other表示的整数绝对值大，所以最终结果的符号为other的符号  
  108.                 result.sign = other.sign;  
  109.                 resultData = subtract(other.data, this.data);  
  110.             } else {  //如果两个数据的位数相同  
  111.                 Integer thisInt = 0;  
  112.                 Integer otherInt = 0;  
  113.                 //从第一位开始比较，直到两者不相等  
  114.                 for (int n = 0; n < thisLength; n++) {  
  115.                     thisInt = new Integer(new String(new byte[]{this.data[n]}));  
  116.                     otherInt = new Integer(new String(new byte[]{other.data[n]}));  
  117.                     if (!thisInt.equals(otherInt)) {   //注意这里要使用equals方法，因为这里需要比较的是两者的内容  
  118.                         break;  
  119.                     }  
  120.                 }  
  121.   
  122.                 //如果this的绝对值大  
  123.                 if (thisInt > otherInt) {  
  124.                     result.sign = this.sign;  
  125.                     resultData = subtract(this.data, other.data);  
  126.                 } else {  
  127.                     result.sign = other.sign;  
  128.                     resultData = subtract(other.data, this.data);  
  129.                 }  
  130.             }  
  131.         }  
  132.         result.data = new byte[resultData.size()];  
  133.         for (int m = 0; m < resultData.size(); m++) {  
  134.             result.data[m] = resultData.get(m);  
  135.         }  
  136.         return result;  
  137.     }  
  138.   
  139.     private ArrayList<Byte> subtract(byte[] larger, byte[] smaller) {  
  140.         ArrayList<Byte> resultData = new ArrayList<Byte>();  
  141.         int flag = 0;  
  142.         int i = smaller.length - 1;  
  143.         int j = larger.length - 1;  
  144.         int k = smaller.length;  
  145.         while (k > 0) {  
  146.             Integer temp = new Integer(new String(new byte[]{larger[j]})) + flag - new Integer(new String(new byte[]{smaller[i]}));  
  147.             if (temp < 0) { //如果相减结果小于0，说明需要借位，则把flag置为 -1，以便下一位减去  
  148.                 flag = -1;  
  149.                 temp += 10;  
  150.             } else {       //如果大于零，需要把flag置为 0.不要忘记了  
  151.                 flag = 0;  
  152.             }  
  153.             resultData.add(0, (temp + "").getBytes()[0]);  
  154.             j--;  
  155.             i--;  
  156.             k--;  
  157.         }  
  158.         //下面的代码就不写注释了  
  159.         while (j >= 0) {  
  160.             Integer temp = new Integer(new String(new byte[]{larger[j]})) + flag;  
  161.             if (temp < 0) {  
  162.                 flag = -1;  
  163.                 temp += 10;  
  164.             } else {  
  165.                 flag = 0;  
  166.             }  
  167.             resultData.add(0, (temp + "").getBytes()[0]);  
  168.             j--;  
  169.         }  
  170.         return resultData;  
  171.     }  
  172.   
  173.   
  174.     @Override  
  175.     public String toString() {  
  176.         String str = new String(this.data);  
  177.         str = getTemp(str);  
  178.         if (sign == '-' && str !="0") {  
  179.             str = sign + str;  
  180.         }  
  181.         return str;  
  182.     }  
  183.   
  184. }  


MyBigIntegerTest.java

[java] view plain copy
  1. import junit.framework.TestCase;  
  2. import java.math.BigInteger;  
  3.   
  4. /** 
  5.  * Created by Rocky on 14-3-26. 
  6.  */  
  7. public class MyBigIntegerTest extends TestCase {  
  8.     public void test1() throws Exception {  
  9.         String a1 = "-5453450543044355356576980545345054545453453454344435353254545345054304435535657698087756454543454345454534534543444353532545453450543044355356454543454354353450136546534534545345345054353450136546534534545345345043044355356576980657698087756454543454354353450136546534534545345345054353450136546534534545345345043044355356576980877564545434543543534501877564545434543543534501";  
  10.         String b1 = "4545453453454344435353254545345054304435535657698087756454543454354345454534534543444353532545453450543044355356576980877564545434545454534534564545434543543534501365465345345453453450543534501365465345345453453450430443553565769804344435353254545345054304435535657698087756454543454354353450136546534534545345345043543534501365465345345453453450534501365465345345453453450";  
  11.         MyBigInteger a = new MyBigInteger(a1);  
  12.         MyBigInteger b = new MyBigInteger(b1);  
  13.         MyBigInteger c = a.add(b);  
  14.         System.out.println(c);  
  15.         BigInteger a2 = new BigInteger(a1);  
  16.         BigInteger b2 = new BigInteger(b1);  
  17.         BigInteger c2 = a2.add(b2);  
  18.         System.out.println(c2);  
  19.         System.out.println(c2.toString().equals(c.toString()));  
  20.     }  
  21. }  


结果：

一个一百亿的计算器的实现

相关推荐