Adding numbers in arrays element by element

Question

The goal is to add two numbers together that are stored in arrays-element by element. The numbers do not necessarily need to be of equal length. I am having trouble accounting for the possibility of a carry over.

If the number is 1101 it would be represented : [1,0,1,1]- The least significant bit is at position 0. I am doing the addition without converting it to an integer.

I am making a separate method to calculate the sum of binary numbers but I just want to understand how to go about this using the same logic.

Ex: 349+999 or they could even be binary numbers as well such as 1010101+11

Any suggestions?

    int carry=0;
    int first= A.length;
    int second=B.length;
    int [] sum = new int [(Math.max(first, second))];
    if(first > second || first==second)
    {
        for(int i =0; i <A.length;i++)
        {
            for(int j =0; j <B.length;j++)
            {
                sum[i]= (A[i]+B[j]);
            }
        }
        return sum; 
    }
    else 
    {
        for(int i =0; i <B.length;i++)
        {
            for(int j =0; j <A.length;j++)
            {
                sum[i]= (A[i]+B[j]);
            }
        }
        return sum;
    }

For the binary addition:

   byte carry=0;
    int first= A.length;
    int second=B.length;
    byte [] sum = new byte [Math.max(first, second)+1];
    if(first > second || first==second)
    {
        for(int i =0; i < A.length && i!= B.length ;i++)
        {
            sum[i]= (byte) (A[i] + B[i] + carry);
            if(sum[i]>1) {
                sum[i] = (byte) (sum[i] -1);
                carry = 1;
            }
            else
                carry = 0;
        }
        for(int i = B.length; i < A.length; i++) {
           sum[i] = (byte) (A[i] + carry);
           if(sum[i]>1) {
                sum[i] = (byte) (sum[i] -1);
                carry = 1;
            }
            else
                carry = 0;
       }
        sum[A.length] = carry; //Assigning msb as carry
        return sum; 
    }
    else 
    { 
        for(int i =0; i < B.length && i!= A.length ;i++) {
            sum[i]= (byte) (A[i] + B[i] + carry);
            if(sum[i]>1) {
                sum[i] = (byte) (sum[i] -1);
                carry = 1;
            }
            else
                carry = 0;
        }
        for(int i = A.length; i < B.length; i++) {
           sum[i] = (byte) (B[i] + carry);
           if(sum[i]>1) {
                sum[i] = (byte) (sum[i] -1);
                carry = 1;
            }
            else
                carry = 0;
       }
        sum[B.length] = carry;//Assigning msb as carry
        return sum; 
    }

How are the numbers represented in the arrays? Is the 0 index the most-significant digit? — Mureinik
– Mureinik, Commented Aug 28, 2015 at 22:43
@Mureinik the least significant bit is represented at the position 0. I added on the problem and made an edit and explained it further — jim
– jim, Commented Aug 28, 2015 at 22:47
if(first > second && first==second) this condition is impossible. If first is equal to second, then it can't be greater than second at the same time. I think you want to use || here instead. — eric.m
– eric.m, Commented Aug 28, 2015 at 22:52

TeasingDart · Accepted Answer · 2015-08-29 02:41:44Z

There is no need to treat binary and decimal differently. This handles any base, from binary to base36, and extremely large values -- far beyond mere int's and long's!

Digits need to be added from the least significant first. Placing the least significant digit first makes the code simpler, which is why most CPUs are Little-Endian.

Note: Save the code as "digits.java" -- digits is the main class. I put Adder first for readability.

Output:

NOTE: Values are Little-Endian! (right-to-left)
base1: 0(0) + 00(0) = 000(0)
base2: 01(2) + 1(1) = 110(3)
base2: 11(3) + 01(2) = 101(5)
base2: 11(3) + 011(6) = 1001(9)
base16: 0A(160) + 16(97) = 101(257)
base32: 0R(864) + 15(161) = 101(1025)

Source code: digits.java:

class Adder {
  private int base;
  private int[] a;
  private int[] b;
  private int[] sum;

  public String add() {
    int digitCt= a.length;
    if(b.length>digitCt)
      digitCt= b.length;        //max(a,b)
    digitCt+= 1;                //Account for possible carry
    sum= new int[digitCt];      //Allocate space
    int digit= 0;               //Start with no carry
    //Add each digit...
    for(int nDigit=0;nDigit<digitCt;nDigit++) {
      //digit already contains the carry value...
      if(nDigit<a.length)
        digit+= a[nDigit];
      if(nDigit<b.length)
        digit+= b[nDigit];
      sum[nDigit]= digit % base;//Write LSB of sum
      digit= digit/base;        //digit becomes carry
    }
    return(arrayToText(sum));
  }

  public Adder(int _base) {
    if(_base<1) {
      base= 1;
    } else if(_base>36) {
      base=36;
    } else {
      base= _base;
    }
    a= new int[0];
    b= new int[0];
  }

  public void loadA(String textA) {
    a= textToArray(textA);
  }

  public void loadB(String textB) {
    b= textToArray(textB);
  }

  private int charToDigit(int digit) {
    if(digit>='0' && digit<='9') {
      digit= digit-'0';
    } else if(digit>='A' && digit<='Z') {
      digit= (digit-'A')+10;
    } else if(digit>='a' && digit<='z') {
      digit= (digit-'a')+10;
    } else {
      digit= 0;
    }
    if(digit>=base)
      digit= 0;
    return(digit);
  }

  private char digitToChar(int digit) {
    if(digit<10) {
      digit= '0'+digit;
    } else {
      digit= 'A'+(digit-10);
    }
    return((char)digit);
  }

  private int[] textToArray(String text) {
    int digitCt= text.length();
    int[] digits= new int[digitCt];
    for(int nDigit=0;nDigit<digitCt;nDigit++) {
      digits[nDigit]= charToDigit(text.charAt(nDigit));
    }
    return(digits);
  }

  private String arrayToText(int[] a) {
    int digitCt= a.length;
    StringBuilder text= new StringBuilder();
    for(int nDigit=0;nDigit<digitCt;nDigit++) {
      text.append(digitToChar(a[nDigit]));
    }
    return(text.toString());
  }

  public long textToInt(String a) {
    long value= 0;
    long power= 1;
    for(int nDigit=0;nDigit<a.length();nDigit++) {
      int digit= charToDigit(a.charAt(nDigit));
      value+= digit*power;
      power= power*base;
    }
    return(value);
  }
}

public class digits {

  public static void main(String args[]) {
    System.out.println("NOTE: Values are Little-Endian! (right-to-left)");
    System.out.println(test(1,"0","00"));
    System.out.println(test(2,"01","1"));
    System.out.println(test(2,"11","01"));
    System.out.println(test(2,"11","011"));
    System.out.println(test(16,"0A","16"));
    System.out.println(test(32,"0R","15"));
  }

  public static String test(int base, String textA, String textB) {
    Adder adder= new Adder(base);
    adder.loadA(textA);
    adder.loadB(textB);
    String sum= adder.add();
    String result= String.format(
      "base%d: %s(%d) + %s(%d) = %s(%d)",
       base,
       textA,adder.textToInt(textA),
       textB,adder.textToInt(textB),
       sum,adder.textToInt(sum)
    );
    return(result);
  }

}

This is really awesome. I just wanted to learn how to do just binary addition by itself with not converting the array to anything and doing it just with it. Could you walk me through your logic on how to do it just with binary?
I created a chat room "binary adder". I will be watching it for the next hour or so.

topched · Accepted Answer · 2015-08-28 23:33:15Z

0

First off, adding binary numbers will be different then ints. For ints you could do something like

int first = A.length;
int second = B.length;

int firstSum = 0;
for (int i = 0; i < first; i++){
    firstSum += A[i] * (10 ^ i);
}

int secondSum = 0;
for (int j = 0; j < second; j++){
    secondSum += B[j] * (10 ^ j);
}

int totalSum = firstSum + secondSum;

edited Aug 28, 2015 at 23:33

answered Aug 28, 2015 at 22:55

topched

7753 silver badges13 bronze badges

6 Comments

jim Over a year ago

Thank you so much. Also, I am making a separate method for calculating binary numbers. How can I adjust my code to fit binary addition?

topched Over a year ago

You will have to read starting at the least significant digit to the most significant digit. So basically reverse the loop. I will leave the adding of binary up to you because this sounds like an assignment. Hint is that there exists a built in function which can convert a binary representation of a number into its integer value

jim Over a year ago

I actually am trying to add it without converting it to an integer value

jim Over a year ago

Just did-I am trying to figure out how to use the carry bit

phuclv Over a year ago

10 ^ i is 10 xor i, not pow(10, i) as you expected

|

burglarhobbit · Accepted Answer · 2015-08-28 23:46:26Z

0

It should be represented like this in below as we have to add only the values at same position of both the arrays. Also, in your first if condition, it should be || instead of &&. This algorithm should perfectly work. Let me know if there are any complications.

int carry=0;
int first= A.length;
int second=B.length;
int [] sum = new int [Math.max(first, second)+1];
if(first > second || first==second)
{
    for(int i =0; i < A.length && i!= B.length ;i++)
    {
        sum[i]= A[i] + B[i] + carry;
        if(sum[i]>9) {
            sum[i] = sum[i] -9;
            carry = 1;
        }
        else
            carry = 0;
    }
    for(int i = B.length; i < A.length; i++) {
       sum[i] = A[i] + carry;
       if(sum[i]>9) {
            sum[i] = sum[i] -9;
            carry = 1;
        }
        else
            carry = 0;
   }
    sum[A.length] = carry; //Assigning msb as carry
    return sum; 
}
else 
{ 
    for(int i =0; i < B.length && i!= A.length ;i++) {
        sum[i]= A[i] + B[i] + carry;
        if(sum[i]>9) {
            sum[i] = sum[i] -9;
            carry = 1;
        }
        else
            carry = 0;
    }
    for(int i = A.length; i < B.length; i++) {
       sum[i] = B[i] + carry;
       if(sum[i]>9) {
            sum[i] = sum[i] -9;
            carry = 1;
        }
        else
            carry = 0;
   }
    sum[B.length] = carry //Assigning msb as carry
    return sum; 
}

edited Aug 28, 2015 at 23:46

answered Aug 28, 2015 at 23:11

burglarhobbit

2,2912 gold badges19 silver badges35 bronze badges

7 Comments

jim Over a year ago

What if I adjusted this for binary numbers- I was trying to and I was going to use instead of 9 being the number that gets carried over but 1 for the binary numbers-does that sound right?

burglarhobbit Over a year ago

If what you are trying to say is if sum[i]>1 for binary then it doesn't seem any wrong to me. Go ahead :) Give it a try.

jim Over a year ago

Ok, so I am using a byte array to represent the binary numbers but that changes the way i can use statements like A[i] + carry and should I change the type for the carry variable to a byte? Or will that limit the kinds of binary numbers I can use?

burglarhobbit Over a year ago

It would be wise to change the data types of carry to byte because you cannot just simply add byte and int data types.

jim Over a year ago

I added what I did using what you gave me but its not working properly. Did I implement it correctly?

|

Collectives™ on Stack Overflow

Adding numbers in arrays element by element

3 Answers 3

2 Comments

6 Comments

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

6 Comments

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related