【华为OJ】【039-无线OSS-高精度整数加法】【华为OJ】【算法总篇章】【华为OJ】【039-无线OSS-高精度整数加法】【工程下载】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
在计算机中，由于处理器位宽限制，只能处理有限精度的十进制整数加减法，比如在32位宽处理器计算机中，
参与运算的操作数和结果必须在-231~231-1之间。如果需要进行更大范围的十进制整数加法，需要使用特殊
的方式实现，比如使用字符串保存操作数和结果，采取逐位运算的方式。如下：
9876543210 + 1234567890 = ?
让字符串 num1="9876543210"，字符串 num2="1234567890"，结果保存在字符串 result = "11111111100"。
-9876543210 + (-1234567890) = ?
让字符串 num1="-9876543210"，字符串 num2="-1234567890"，结果保存在字符串 result = "-11111111100"。

要求编程实现上述高精度的十进制加法。
要求实现方法： 
public String add (String num1, String num2)
【输入】num1：字符串形式操作数1，如果操作数为负，则num1的前缀为符号位'-'
num2：字符串形式操作数2，如果操作数为负，则num2的前缀为符号位'-'
【返回】保存加法计算结果字符串，如果结果为负，则字符串的前缀为'-'

注：
(1)当输入为正数时，'+'不会出现在输入字符串中；当输入为负数时，'-'会出现在输入字符串中，且一定在输入字符串最左边位置；
(2)输入字符串所有位均代表有效数字，即不存在由'0'开始的输入字符串，比如"0012", "-0012"不会出现；
(3)要求输出字符串所有位均为有效数字，结果为正或0时'+'不出现在输出字符串，结果为负时输出字符串最左边位置为'-'。

1
2
输入两个字符串

1
2
输出给求和后的结果

1
2
3
9876543210
1234567890

1
2
11111111100

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
import java.util.Scanner;

/**
 * Author: 王俊超
 * Date: 2015-12-24 17:18
 * All Rights Reserved !!!
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
//        Scanner scanner = new Scanner(Main.class.getClassLoader().getResourceAsStream("data2.txt"));
        while (scanner.hasNext()) {

            String n = scanner.next();
            String m = scanner.next();
            // 【1】方法一
            System.out.println(add(n, m));

            // 【2】方法二
//            BigInteger bi1 = new BigInteger(n);
//            BigInteger bi2 = new BigInteger(m);
//            System.out.println(bi1.add(bi2));
        }

        scanner.close();
    }

    /**
     * 大整数相加，n、m都为自然数
     *
     * @param ns 数字
     * @param ms 数字
     * @return 结果
     */
    private static String add(String ns, String ms) {


        // ns是否为正数
        boolean pn = ns.charAt(0) != '-';
        // ms是否为正数
        boolean pm = ms.charAt(0) != '-';

        int[] n;
        int[] m;
        if (pn) {
            n = getNumber(ns);
        } else {
            n = getNumber(ns.substring(1));
        }

        if (pm) {
            m = getNumber(ms);
        } else {
            m = getNumber(ms.substring(1));
        }


        // 两者同号
        if (pn == pm) {
            // 进行计算
            int[] r = add(m, n);
            String rs = toNumber(r);

            // 根据需要添加负号
            if (pn) {
                return rs;
            } else {
                return "-" + rs;
            }
        } else {
            // ns的绝对值比大于等于ms
            if (compare(n, m) >= 0) {
                int[] r = minus(n, m);
                String rs = toNumber(r);
                // ns为正数，ms为负数
                if (pn) {
                    return rs;
                } else {
                    return "-" + rs;
                }
            }
            // ns的绝对值比小于ms
            else {
                int[] r = minus(m, n);
                String rs = toNumber(r);

                // ns为正数，ms为负数
                if (pn) {
                    return "-" + rs;

                } else {
                    return rs;
                }
            }
        }
    }

    /**
     * 两个整数相加
     *
     * @param m 整数
     * @param n 整数
     * @return 结果
     */
    private static int[] add(int[] m, int[] n) {

//        System.out.println(Arrays.toString(n) +"n"+ Arrays.toString(m));

        // 保证n不小于m
        if (m.length > n.length) {
            int[] t = m;
            m = n;
            n = t;
        }

        // 结果的最大长度
        int[] r = new int[n.length + 1];
        // 来自低位的进位
        int c = 0;

        for (int i = 0; i < m.length; i++) {
            r[i] = m[i] + n[i] + c;
            c = r[i] / 10;
            r[i] %= 10;
        }

        // 计算余下的部分
        for (int i = m.length; i < n.length; i++) {
            r[i] = n[i] + c;
            c = r[i] / 10;
            r[i] %= 10;
        }

//        System.out.println(Arrays.toString(n) +"n"+ Arrays.toString(m) + "n" + Arrays.toString(r));

        // 最后还有进位
        if (c != 0) {
            r[r.length - 1] = c;
            return r;
        }
        // 没有进位
        else {
            int[] ret = new int[r.length - 1];
            System.arraycopy(r, 0, ret, 0, ret.length);
            return ret;
        }
    }


    /**
     * 比较两个整数是否相等，下标由小到大表示由低位到高位，忽略最高有效位上的前导0
     *
     * @param m 整数
     * @param n 整数
     * @return m > n返回1，m = n返回0，m < n返回-1
     */
    private static int compare(int[] m, int[] n) {

        if (m == null && n == null) {
            return 0;
        }
        // null最小
        if (m == null) {
            return -1;
        }

        if (n == null) {
            return 1;
        }

        int lastM = m.length - 1;
        int lastN = n.length - 1;

        // 找m的最高有效位的位置，至少有一位
        while (lastM >= 1 && m[lastM] == 0) {
            lastM--;
        }
        // 找n的最高有效位的位置，至少有一位
        while (lastN >= 1 && n[lastN] == 0) {
            lastN--;
        }

        // m的数位比n多，说明m比n大
        if (lastM > lastN) {
            return 1;
        }
        // m的数位比n少，说明m比n小
        else if (lastM < lastN) {
            return -1;
        } else {
            // 位数一样，比较每一个数位上的值，从高位到低位进行比较
            for (int i = lastM; i >= 0; i--) {
                if (m[i] > n[i]) {
                    return 1;
                } else if (m[i] < n[i]) {
                    return -1;
                }
            }

            return 0;
        }
    }


    /**
     * 做减法n-m，保证n大于等于m
     *
     * @param n 整数
     * @param m 整数
     * @return 结果
     */
    private static int[] minus(int[] n, int[] m) {

        n = format(n);
        m = format(m);

        int[] r = new int[n.length];

        // 当前位被借位
        int c = 0;
        int t;
        for (int i = 0; i < m.length; i++) {
            t = n[i] - c - m[i];
            // 当前位够减
            if (t >= 0) {
                r[i] = t;
                // 没有进行借位
                c = 0;
            }
            // 不够减
            else {
                r[i] = t + 10;
                // 进行借位
                c = 1;
            }
        }

         // 还有借位或者n比m位数多，要将n中的数位复制到r中
        for (int i = m.length; i < n.length; i++) {
            t = n[i] - c;
            // 当前位够减
            if (t >= 0) {
                r[i] = t;
                // 没有进行借位
                c = 0;
            }
            // 不够减
            else {
                r[i] = t + 10;
                // 进行借位
                c = 1;
            }
        }

        return format(r);
    }


    /**
     * 将整数字符串表示成整数数组【包含符号位】
     *
     * @param n 整数字符串
     * @return 整数数组 下标从小到大表示数位的从低到高
     */
    private static int[] getNumber(String n) {
        int[] r = new int[n.length()];
        for (int i = 0; i < r.length; i++) {
            r[i] = n.charAt(n.length() - i - 1) - '0';
        }

        return r;
    }

    /**
     * 将整数进行格式化，去掉高位的前导0
     *
     * @param r 整数
     * @return 结果
     */
    private static int[] format(int[] r) {
        int t = r.length - 1;
        // 找最高有效位
        while (t > 0 && r[t] == 0) {
            t--;
        }

        int[] nr = new int[t + 1];
        System.arraycopy(r, 0, nr, 0, nr.length);
        return nr;

    }


    /**
     * 将数组表示的整数转换成字符串
     *
     * @param r 整数
     * @return 字符串表示的整数
     */
    private static String toNumber(int[] r) {
        if (r == null) {
            return null;
        }

        StringBuilder b = new StringBuilder(r.length);

        for (int i = r.length - 1; i >= 0; i--) {
            b.append(r[i]);
        }

        return b.toString();
    }
}