# Adding two big integers represented as strings

Posted on

Problem

``````class MyClass{
static Integer carry = 0;
public static void main(String args[]){
String s1 = "7654729850328997631007285998163550104";
String s2 = "5980139243970186632651869926335829102";
}

public static void add(String a, String b){
ArrayList<String> res = new ArrayList<String>();
StringBuilder myString = null;
int i = a.length() - 1;
int j = b.length() - 1;
while(true){
int i1 = Integer.parseInt(Character.toString(a.charAt(i)));
int i2 = Integer.parseInt(Character.toString(b.charAt(j)));
Integer i3  = i1 + i2 + carry;
if(i3 > 9){
carry = 1;
i3 = i3 - 10;
}else carry = 0;
i--;j--;
if(i < 0){
break;
}
}
Collections.reverse(res);
for(String r : res){
System.out.print(r);
}
}
}
``````

This program adds 2 numbers whose length is greater than limit of Long. I think my logic is kind of bulky. Can something be done to improve this?

Solution

Loop structure’s OK, logic’s reasonably good. There is obviously a Java library alternative of `BigInteger`, but I assume you knew that. Some efficiency issues with excessive toString() and string-ification of what could be character operations.

Here are some tips:

1. Use `int` where nulls are not possible, not `Integer`.
2. `carry` is only used locally — keep it local. Referencing it outside the method can only be erroneous, so it shouldn’t be visibly exposed to make that possible..
3. Carry calculation from `i3` is OK here, but could in related algorithms be brittle — it can’t handle a digit-sum > 19 as the maximum carry it can produce is 1.
4. If addition completes with a carry of 0, it will output an unnecessary 0 digit.
5. If Strings are your inputs, you should probably build a String as the result via a StringBuilder — not an ArrayList.
6. `myString` should be called `result` or `sb`, if you’re building the result in it.
7. Build using StringBuilder in reverse order, and do it by character calculation `(char) (i3 + '0')` rather than toString() if you want to maximize efficiency.
8. Return the result from your function, and do the printing in main() instead. there. That way you have a general-purpose `add()` function and a fixed-purpose main() method for testing.

Is that complete enough?

This is only a partial refactoring, I have extracted some methods and fixed some problems. For example: if the two numbers have different lenghts, your program throws an exception:

``````Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String index out of range: -1
at java.lang.String.charAt(Unknown Source)
at it.test.refactor.MyClass.main(MyClass.java:11)
``````

I’ll do some more refactoring later ðŸ™‚

``````package it.test.refactor;

import java.util.regex.Pattern;

public class Main {

private static final String DEFAULT1 = "00033000010";
private static final String DEFAULT2 = "1";

public static void main(String[] args) {
if (args.length == 1 || args.length > 2) {
System.err.println("Usage: MyClass integer1 integer2n n exemple: MyClass 123432 4321234");
return;
}
if (args.length == 0) {
System.out.println("Warning: using default parameters: " + DEFAULT1 + " + " + DEFAULT2);
} else {
}
}
}

class TextualNumbers {

private static Pattern onlyDigits = Pattern.compile("\A[0-9]*\z");

PartialInputProcessor resultWithCarry = new PartialInputProcessor(0);
StringBuilder res = new StringBuilder(maxLen + 1);
for (int charIndex = 0; charIndex < maxLen; charIndex++) {
int first = parseIntOrGet0(firstAddend, firstAddend.length() - charIndex - 1);
int second = parseIntOrGet0(secondAddend, secondAddend.length() - charIndex - 1);
resultWithCarry.processInputs(first, second);
res.append(resultWithCarry.getPartialResult());
}
res.append(String.valueOf(resultWithCarry.getCarry()));
String response = trimLeadingZeros(res.reverse().toString());
return response;
}

private void validate(String addend) {
if (addend == null) {
throw new NullPointerException();
}
if (addend.length() == 0) {
throw new IllegalArgumentException("[ " + addend + " ] is not a positive integer.");
}

throw new IllegalArgumentException("[ " + addend + " ] is   not a positive integer.");
}
}

private int parseIntOrGet0(String intString, int charPosition) {
if (intString.length() <= charPosition || charPosition < 0) {
return 0;
} else {
return Character.digit(intString.charAt(charPosition), 10);
}
}

private String trimLeadingZeros(String a) {
while (a.startsWith("0")) {
a = a.substring(1);
}
return a;
}

}

class PartialInputProcessor {

private int carry;
private String partialResult;

public PartialInputProcessor(int initialCarry) {
this.carry = 0;
}

public String getCarry() {
return String.valueOf(carry);
}

public String getPartialResult() {
return partialResult;
}

public void processInputs(int input1, int input2) {
int partialSum = input1 + input2 + carry;
carry = partialSum / 10;
partialResult = String.valueOf(partialSum % 10);
}

}
``````

Your code breaks if the input strings are of different lengths.

It is important to note that you don’t support negative or non-integer inputs.

I would expect the `add()` function to return the result as a String: `public static String add(String a, String b)`. (You probably intended to do that, since you declared `myString` but never used it.)

Instead of accumulating the result in an `ArrayList<String>`, I would just use the `StringBuilder`. (`StringBuilder` is essentially an `ArrayList` of `char`. It even has a `.reverse()` method.)

The `carry` variable should be local to the `add()` function; there is no reason why it should be stored in the state of the class. It’s confusing, and it makes your code non-thread-safe. (Also, `int` should be preferred over `Integer` whenever possible.)

`MyClass` is a pointless name. `BigInteger` would be a good name, but it would be a bad idea to use the same name as a class in the standard Java library, even if they are in different packages. Name it something similar to `BigInteger`.

Your variable names could be improved with parallelism. It’s hard to remember that `i1` and `i` correspond to `a`, and `i2` and `j` correspond to `b`. Naming the variables `digit1`, `i1`, `addend1` and `digit2`, `i2`, `addend2` would be better.

A `while (true) { â€¦ }` loop with a `break` inside suggests that the code structure could be improved. I think that a for-loop provides a better structure.

``````/**
* Adds two non-negative integers represented as string of digits.
*
* @exception NumberFormatException if either argument contains anything other
*            than base-10 digits.
*/
StringBuilder buf = new StringBuilder();
for ( int i1 = addend1.length() - 1, i2 = addend2.length() - 1, carry = 0;
i1 >= 0 || i2 >= 0 || carry != 0;
i1--, i2-- ) {
int digit1 = i1 < 0 ? 0 :
int digit2 = i2 < 0 ? 0 :

int digit = digit1 + digit2 + carry;
if (digit > 9) {
carry = 1;
digit -= 10;
} else {
carry = 0;
}

buf.append(digit);
}
return buf.reverse().toString();
}
``````

Loop structure’s OK, logic’s reasonably good. There is obviously a Java library alternative of `BigInteger`, but I assume you knew that. Some efficiency issues with excessive toString() and string-ification of what could be character operations.

Here are some tips:

1. Use `int` where nulls are not possible, not `Integer`.
2. `carry` is only used locally — keep it local. Referencing it outside the method can only be erroneous, so it shouldn’t be visibly exposed to make that possible..
3. Carry calculation from `i3` is OK here, but could in related algorithms be brittle — it can’t handle a digit-sum > 19 as the maximum carry it can produce is 1.
4. If addition completes with a carry of 0, it will output an unnecessary 0 digit.
5. If Strings are your inputs, you should probably build a String as the result via a StringBuilder — not an ArrayList.
6. `myString` should be called `result` or `sb`, if you’re building the result in it.
7. Build using StringBuilder in reverse order, and do it by character calculation `(char) (i3 + '0')` rather than toString() if you want to maximize efficiency.
8. Return the result from your function, and do the printing in main() instead. there. That way you have a general-purpose `add()` function and a fixed-purpose main() method for testing.

Is that complete enough?

This is my version with basic java API’s

``````package geeks.in.action.algo.numtoword;

public class AddTwoBigNumbers {

public static void main(String[] args) {
try {
} catch (final Exception e) {
System.out.println("Exception : " + e.getMessage());
}
}

private static String addIntegers(String number1, String number2) throws Exception {
validate(number1, number2);
System.out.println("Adding: " + number1 + "+" + number2);
char[] num1char = number1.toCharArray();
char[] num2char = number2.toCharArray();
if (num1char.length > num2char.length) {
num2char = formatToSameLength(num1char, num2char);
} else if (num1char.length < num2char.length) {
num1char = formatToSameLength(num2char, num1char);
}
final char[] addition = new char[num1char.length + 1];
char carrry = '0';
for (int i = num1char.length - 1; i >= 0; i--) {
final int sum = Character.getNumericValue(num1char[i]) + Character.getNumericValue(num2char[i]) + Character.getNumericValue(carrry);
final char[] csum = String.valueOf(sum).toCharArray();
carrry = '0';
if (csum.length > 1 && i == 0) {
addition[i + 1] = csum[1];
} else if (csum.length > 1) {
carrry = csum[0];
addition[i + 1] = csum[1];
} else {
addition[i + 1] = csum[0];
}
}
}

private static void validate(String number1, String number2) throws Exception {
if (number1.trim().isEmpty() || number2.trim().isEmpty() || !isNumber(number1) || !isNumber(number2)) {
throw new Exception("Number is not present or not a valid number");
}
}

private static boolean isNumber(String number) {
try {
Integer.parseInt(number);
return true;
} catch (final NumberFormatException nfe) {
}
return false;
}

private static char[] formatToSameLength(char[] num1char, char[] num2char) {
final int diff = num1char.length - num2char.length;
final char[] num = new char[num1char.length];
for (int i = 0; i < diff; i++) {
num[i] = '0';
}
for (int i = 0; i < num2char.length; i++) {
num[diff + i] = num2char[i];
}
return num;
}
}
``````