源地址：

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

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

MyBigInteger.java

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

MyBigIntegerTest.java

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