我最近遇到了一个编程难题,我终其一生都找不到满意的答案:计算由字符串给出的两个任意大整数的总和,其中第二个整数可能为负数。这是在 Java 中完成的,无需使用任何 BigInteger
、BigNumber
等类。
我最初的方法是伪代码如下:
- 如果第二个字符串的第一个字符是'-'则设置减法标志。
- 将每个字符串转换为一个整数数组,每个数字一个。
- 扩展最短的数组并在左侧填充零,使两个数组的大小相同。
- 遍历数组的每个索引(从最低有效位到最高有效位)执行加法/减法,并使用进位将溢出转移到下一位。
- 检查进位以添加任何最后的数字。
我的算法对正数运行良好,但对负数给出非常错误的结果。我试图在纸上解决这个问题,但我似乎无法理解如何逐位减法。
我当前的第 4 步和第 5 步算法如下:
int[] result = new int[number1.length];
int carry = 0;
for(int i = number1.length - 1; i >= 0; i--) {
int newDigit = (negative ? number1[i] - number2[i] : number1[i] + number2[i]);
newDigit += carry;
if (newDigit >= 10) {
carry = 1;
newDigit -= 10;
} else if (newDigit < 0) {
carry = -1;
newDigit += 10;
} else {
carry = 0;
}
result[i] = newDigit;
}
// Convert result back into a string.
String resultString = intArrayToString(result);
// Apply carry.
if(carry == 1) {
return "1" + resultString;
} else if(carry == -1) {
return "-" + resultString;
} else {
return resultString;
}
最佳答案
如果符号为负且 number2 大于 number1,您可以简单地交换这些整数数组。
你可以尝试这样的事情:
boolean swap = false;
for(int j = 0; j < number1.length && negative; j++){
if(number2[j] > number1[j]){
swap = true;
int temp[] = number1;
number1 = number2;
number2 = temp;
break;
} else if(number1[j] > number2[j]){
break;
}
}
int[] result = new int[number1.length];
int carry = 0;
for(int i = number1.length - 1; i >= 0; i--) {
int newDigit = (negative ? number1[i] - number2[i] : number1[i] + number2[i]);
newDigit += carry;
if (newDigit >= 10) {
carry = 1;
newDigit -= 10;
} else if (newDigit < 0) {
carry = -1;
newDigit += 10;
} else {
carry = 0;
}
result[i] = newDigit;
}
// Convert result back into a string.
String resultString = "";
for(int j = 0; j <result.length; j++){
resultString += (result[j] + "");
}
// Apply carry.
if(carry == 1) {
return "1" + resultString;
} else if(carry == -1 || swap) {//if swap is set sign is -
return "-" + resultString;
} else {
return resultString;
}
关于java - 两个整数一位一位地相减,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21250041/