java - Java中大数的加法和减法
问题描述
我有这个任务，我应该在其中添加或减去非常大的数字（超长）。我需要使用 String 和/或 StringBuilder 使其工作。
我在这里有一些代码，但大多数情况下都不起作用，而且减法确实有问题。
/** This class contains the method meant to calculate the sum of two large numbers.
*/
public class SummingLargeNumbers {
private SummingLargeNumbers() {}
private static final char ZERO = '0';
/**
* Implements addition of two large numbers.
*
* @param s1 First number as string.
* @param s2 Second number as string.
* @return The answer as a string.
*/
static String findSum(String s1, String s2) {
if (s1 == null || s2 == null || s1.equals("") || s2.equals("")) {
return "";
}
if (s1.length() > s2.length()) {
String temp = s1;
s1 = s2;
s2 = temp;
}
StringBuilder result = new StringBuilder();
int n1 = s1.length();
int n2 = s2.length();
int diff = n2 - n1;
int denom = 0;
for (int i = n1 - 1; i >= 0; i--) {
int sum = ((int) (s1.charAt(i) - ZERO) + (int) (s2.charAt(i + diff) - ZERO) + denom);
result.append((char) (sum % 10 + ZERO));
denom = sum / 10;
}
for (int i = n2 - n1 - 1; i >= 0; i--) {
int sum = ((int) (s2.charAt(i) - ZERO) + denom);
result.append((char) (sum % 10 + ZERO));
denom = sum / 10;
}
if (denom > 0) {
result.append((char) (denom + ZERO));
}
return result.reverse().toString();
}
/**
* Checks whether the first number is smaller than the second.
*
* @param s1 First number as a string.
* @param s2 Second number as a string.
* @return True if the first number is smaller than the second and false if otherwise.
*/
static boolean isSmaller(String s1, String s2) {
int firstLength = s1.length();
int secondLength = s2.length();
if (firstLength < secondLength) return true;
if (secondLength < firstLength) return false;
for (int i = 0; i < firstLength; i++) {
if (s1.charAt(i) < s2.charAt(i)) return true;
else if (s1.charAt(i) > s2.charAt(i)) return false;
}
return false;
}
/**
* Implements subtraction of two large numbers.
*
* @param s1 First number as a string.
* @param s2 Second number as a string.
* @return The answer as a string.
*/
static String findDiff(String s1, String s2) {
if (s1 == null || s2 == null || s1.equals("") || s2.equals("")) {
return "";
}
if (isSmaller(s1, s2)) {
String temp = s1;
s1 = s2;
s2 = temp;
}
StringBuilder result = new StringBuilder();
int n1 = s1.length();
int n2 = s2.length();
int diff = n1 - n2;
int denom = 0;
for (int i = n2 - 1; i >= 0; i--) {
int sum =
(((int) s1.charAt(i + diff) - (int) '0') - ((int) s2.charAt(i) - (int) '0') - denom);
if (sum < 0) {
sum = sum + 10;
denom = 1;
} else {
denom = 0;
}
result.append(String.valueOf(sum));
}
for (int i = n1 - n2 - 1; i >= 0; i--) {
if (s1.charAt(i) == '0' && denom > 0) {
result.append("9");
continue;
}
int sub = (((int) s1.charAt(i) - (int) '0') - denom);
if (i > 0 || sub > 0) {
result.append(String.valueOf(sub));
denom = 0;
}
}
if (result.reverse().indexOf("0") == 0) {
result.deleteCharAt(0);
}
return result.toString();
}
}
我真的不明白我哪里出错了，现在我还必须在一种方法中实现加法和减法，这对我来说真的很难。如果我能对整个事情有所了解，我会很高兴，这样我就可以尝试让它发挥作用。
例如，一些不起作用的情况是：
-88131415555612 + 77020304444501 = 11111111111111
在这种情况下，它应该返回 -11111111111111
-1021315510 + 2183194 = 1019132316
在这里它也应该返回 -1019132316
大多数与减法有关的情况都是错误的。
解决方案
这看起来是一个有趣的问题，所以我试了一下。这是我最近一次测试的结果。
123 + 8900 = 9023
123 + 89 = 212
-123 + 893 = 770
-123 + -893 = -1016
123 + -893 = -770
999 + -999 = 0
999 + -997 = 2
-999 + 997 = -2
-88131415555612 + 77020304444501 = -11111111111111
-1021315510 + 2183194 = -1019132316
1021315510 + -2183194 = 1019132316
-1021315510 + -2183194 = -1023498704
我无法理解您的代码。你有太多的静态方法。如果您想知道，太多的静态字段和方法是一件需要避免的坏事。
所以，这就是你如何处理这样的问题。
将问题分解为越来越小的步骤，直到您可以对每个步骤进行编码。
这就是我的意思：
Sum two String numbers
Return empty string if either String number is null or empty.
Determine if the first String has a negative sign.
Determine if the second string has a negative sign.
If the signs are the same
Add numbers.
Else
Subtract numbers.
Add numbers
Determine if the first String has a negative sign.
Strip signs from both numbers.
Add numbers, starting from the right and going left.
Append the carry, if any.
Append the negative sign, if needed.
Subtract numbers
Order the numbers by absolute value, largest first, then smallest.
Determine if the largest String has a negative sign.
Strip signs from both numbers.
Subtract the smaller from the larger, starting from the right and going left.
Append the negative sign, if needed.
Remove leading zeros.
当然，这在您编写完代码之后会容易得多。
从小处着手。我首先得到了相同的标志。然后我研究了相反的符号加法（减法）。
像一篇文章一样组织你的代码。先放最抽象的代码，然后是更详细的代码。阅读您的代码的人永远不必回头查看顶部以了解某些内容是如何工作的。
这是完整的可运行代码。
public class SummingLargeNumbers {
public static void main(String[] args) {
SummingLargeNumbers sln = new SummingLargeNumbers();
String s1 = "123";
String s2 = "8900";
System.out.println(s1 + " + " + s2 + " = " + sln.findSum(s1, s2));
s1 = "123";
s2 = "89";
System.out.println(s1 + " + " + s2 + " = " + sln.findSum(s1, s2));
s1 = "-123";
s2 = "893";
System.out.println(s1 + " + " + s2 + " = " + sln.findSum(s1, s2));
s1 = "-123";
s2 = "-893";
System.out.println(s1 + " + " + s2 + " = " + sln.findSum(s1, s2));
s1 = "123";
s2 = "-893";
System.out.println(s1 + " + " + s2 + " = " + sln.findSum(s1, s2));
s1 = "999";
s2 = "-999";
System.out.println(s1 + " + " + s2 + " = " + sln.findSum(s1, s2));
s1 = "999";
s2 = "-997";
System.out.println(s1 + " + " + s2 + " = " + sln.findSum(s1, s2));
s1 = "-999";
s2 = "997";
System.out.println(s1 + " + " + s2 + " = " + sln.findSum(s1, s2));
s1 = "-88131415555612";
s2 = "77020304444501";
System.out.println(s1 + " + " + s2 + " = " + sln.findSum(s1, s2));
s1 = "-1021315510";
s2 = "2183194";
System.out.println(s1 + " + " + s2 + " = " + sln.findSum(s1, s2));
s1 = "1021315510";
s2 = "-2183194";
System.out.println(s1 + " + " + s2 + " = " + sln.findSum(s1, s2));
s1 = "-1021315510";
s2 = "-2183194";
System.out.println(s1 + " + " + s2 + " = " + sln.findSum(s1, s2));
}
public String findSum(String s1, String s2) {
if (s1 == null || s2 == null || s1.isEmpty() || s2.isEmpty()) {
return "";
}
boolean s1IsNegative = s1.charAt(0) == '-';
boolean s2IsNegative = s2.charAt(0) == '-';
if (s1IsNegative == s2IsNegative) {
return addNumbers(s1, s2);
} else {
return subtractNumbers(s1, s2);
}
}
private String addNumbers(String s1, String s2) {
boolean s1IsNegative = s1.charAt(0) == '-';
s1 = stripSign(s1);
s2 = stripSign(s2);
int index1 = s1.length() - 1;
int index2 = s2.length() - 1;
int carry = 0;
StringBuilder builder = new StringBuilder();
// Add the two String numbers together;
while (index1 >= 0 || index2 >= 0) {
int digit1 = (index1 >= 0) ? convertToInt(s1.charAt(index1--)) : 0;
int digit2 = (index2 >= 0) ? convertToInt(s2.charAt(index2--)) : 0;
int sum = digit1 + digit2 + carry;
carry = sum / 10;
int digit = sum % 10;
builder.append(digit);
}
if (carry > 0) {
builder.append(carry);
}
if (s1IsNegative) {
builder.append('-');
}
return builder.reverse().toString();
}
private String subtractNumbers(String s1, String s2) {
String[] order = orderNumbers(s1, s2);
String larger = order[0];
String smaller = order[1];
boolean largerIsNegative = larger.charAt(0) == '-';
larger = stripSign(larger);
smaller = stripSign(smaller);
int index1 = larger.length() - 1;
int index2 = smaller.length() - 1;
int borrow = 0;
StringBuilder builder = new StringBuilder();
// Subtract the smaller from the larger String number
while (index1 >= 0 || index2 >= 0) {
int digit1 = (index1 >= 0) ? convertToInt(larger.charAt(index1--)) : 0;
int digit2 = (index2 >= 0) ? convertToInt(smaller.charAt(index2--)) : 0;
int difference = digit1 - digit2 - borrow;
if (difference < 0) {
difference += 10;
borrow = 1;
} else {
borrow = 0;
}
builder.append(difference);
}
if (largerIsNegative) {
builder.append('-');
}
return removeLeadingZeros(builder);
}
/**
* This method returns the String numbers in absolute value order.
*
* @param s1 - String number 1
* @param s2 - String number 2
* @return - String array consisting of two values. The largest absolute value
* is first and the smallest absolute value is second.
*/
private String[] orderNumbers(String s1, String s2) {
boolean s1IsNegative = s1.charAt(0) == '-';
boolean s2IsNegative = s2.charAt(0) == '-';
s1 = stripSign(s1);
s2 = stripSign(s2);
String largest;
String smallest;
if (s1.length() < s2.length()) {
largest = (s2IsNegative) ? "-" + s2 : s2;
smallest = (s1IsNegative) ? "-" + s1 : s1;
} else if (s1.length() > s2.length()) {
largest = (s1IsNegative) ? "-" + s1 : s1;
smallest = (s2IsNegative) ? "-" + s2 : s2;
} else {
boolean s1IsLarger = true;
// Both Strings are the same size. Find the largest digit,
// starting from left to right;
for (int index = 0; index < s1.length(); index++) {
int digit1 = convertToInt(s1.charAt(index));
int digit2 = convertToInt(s2.charAt(index));
if (digit1 < digit2) {
s1IsLarger = false;
break;
} else if (digit2 < digit1) {
s1IsLarger = true;
break;
}
}
if (s1IsLarger) {
largest = (s1IsNegative) ? "-" + s1 : s1;
smallest = (s2IsNegative) ? "-" + s2 : s2;
} else {
largest = (s2IsNegative) ? "-" + s2 : s2;
smallest = (s1IsNegative) ? "-" + s1 : s1;
}
}
String[] output = new String[2];
output[0] = largest;
output[1] = smallest;
return output;
}
private String removeLeadingZeros(StringBuilder builder) {
int index = builder.length() - 1;
boolean isNegative = builder.substring(index, index + 1).equals("-");
if (isNegative) {
builder.delete(index, index + 1);
index--;
}
while (index > 0) {
if (builder.substring(index, index + 1).equals("0")) {
builder.delete(index, index + 1);
index--;
} else {
break;
}
}
if (isNegative) {
builder.append('-');
}
return builder.reverse().toString();
}
private String stripSign(String s) {
if (s.charAt(0) == '-' || s.charAt(0) == '+') {
return s.substring(1);
} else {
return s;
}
}
private int convertToInt(char c) {
return (int) (c - '0');
}
}
推荐阅读
- octave - 使用 Octave 求解 ODE 系统
- uml - 在 EA 中从源代码生成组件图
- fullcalendar - 在全日历中显示约会的两个问题
- javascript - 如何在echart图例中添加更多内容？
- elasticsearch - 改进 ElasticSearch 索引的各种方法是什么？
- python - Matplotlib 白色椭圆在没有轴的彩色背景上
- r - R 如何创建包含多个 txt 文件中的文本的列表？
- functional-programming - F#：整数到整数对
- selenium - Selenium - 测试不点击菜单项，但如果我点击它，测试完成
- android - 如何使跨度计数和图标大小自动