Binary Addition

[Deo Favente]

Ok iv'e been stuck on this for a long time and i still can't get it to work. Binary addition given two arrays of booleans (binary numbers) that must be recursive and return an array of booleans. When i post my code i have so far that usually becomes the focus and everyone gets confused or goes off topic so im not doing it this time. And its binary addition not convert-to-decimal-and-use-jvm-to-add.

[sukatoa]

Will you post your algorithm on binary addition?

or sight some adding example.....

I know it in assembly, maybe we could formulate that here in java....

[Eranga]

Yes, if you don't put your code here at this point, tell me about the logic/algorithm you workout.

[Deo Favente]

This is what iv'e been doing:
1) I found the smaller array, and then made it the same length as the big array
2) I ran each element through a loop to compare the same index in both arrays
3) If both booleans are false, set the index in the final array false
If one is true, set the final boolean true
If both are true, then i make a new number that has 1 true in front followed by all false, so that the true is one ahead of the current index, thenm i add the temporary array to the final array (this is generally where i run into problems)

[Eranga]

From the beginning I'm stuck.

Quote:

Originally Posted by Deo Favente

1) I found the smaller array, and then made it the same length as the big array

What you mean smaller array and big array. Since you use the word 'same length' I can't figure out what is the different of smaller and big. It's better to make it more clear.

[Deo Favente]

well the two arrays most likey arn't going to be the same size, and if you try to run a for loop going thru each loop at the same time ur gonna get a out of bounds error so i need to continue to prepend the arrays so that they both align up, like how we do addition. When we do addition and the numbers arn't the same length we know that there's as many zeros in fron of the shorter number as we need there to be.

[Eranga]

Ok, I got the point. What you have done up to now.

[Deo Favente]

everything except the last part of 3

[Eranga]

After comparing two arrays with the same index, you can find the result, that both are false, only one or both are true. Is that right?

Next, can you refer the same index of the final array? If so why can't you refer the previous index?

[danielstoner]

Hi Deo, here is your algorithm if I understood the problem

Code:

package test;

import java.util.*;

public class BinaryAdd
{
    private static boolean [] add(boolean [] a, boolean [] b)
    {
        // pad them to same length
        int l = a.length > b.length ? a.length : b.length;
        a = Arrays.copyOf(a, l);
        b = Arrays.copyOf(b, l);

        // prevent overflow, make the results bigger
        boolean [] r = new boolean[a.length + 1];
        boolean t = false;

        for (int i = 0; i < l; i++)
        {
            if (a[i] &&  b[i])
            {
                if (t)
                {
                    r[i] = true;
                    t = true;
                }
                else
                {
                    r[i] = false;
                    t = true;
                }
            }
            else if (a[i] ||  b[i])
            {
                if (t)
                {
                    r[i] = false;
                    t = true;
                }
                else
                {
                    r[i] = true;
                    t = false;
                }
            }
            else
            {
                if (t)
                {
                    r[i] = true;
                    t = false;
                }
                else
                {
                    r[i] = false;
                    t = false;
                }
            }
        }

        // check overflow
        if (t)
        {
            r[l] = true;
        }

        return r;
    }

    public static void main(String[] args)
    {
        // least significant position is at 0
        boolean a1[] = {true};
        boolean a2[] = {false};
        boolean a3[] = {true, true};
        boolean a4[] = {false, false};
        boolean a5[] = {true, false};
        boolean a6[] = {false, true};

        boolean a7[] = {true, true, true, true};
        boolean a8[] = {false, true, false, true};

        // keep in mind least significant value is at index 0
        System.out.println(Arrays.toString(a1) + " + " + Arrays.toString(a1) + " = " + Arrays.toString(add(a1, a1)));
        System.out.println(Arrays.toString(a1) + " + " + Arrays.toString(a2) + " = " + Arrays.toString(add(a1, a2)));
        System.out.println(Arrays.toString(a3) + " + " + Arrays.toString(a3) + " = " + Arrays.toString(add(a3, a3)));
        System.out.println(Arrays.toString(a7) + " + " + Arrays.toString(a8) + " = " + Arrays.toString(add(a7, a8)));
    }
}

[Deo Favente]

ok thanks that works well. I'm actually using a class that contains a boolean array for my implementation but it fits right in. I see now where i went wrong, and you have also provided a more efficent way of aligning the arrays to do the addition. Thanks a bunch

[danielstoner]

You are welcome. It was fun to implement