Algorithm for binary arithmetic in Java

Question

On paper, binary arithmetic is simple, but as a beginning programmer, I'm finding it a little difficult to come up with algorithms for the addition, subtraction, multiplication and division of binary numbers.

I have two binary numbers stored as strings, assume that any leading zeroes have been dropped. How would I go about performing these operations on the two numbers?

Edit: I need to avoid converting them to an int or long.

Solution 1

The following code implements binary addition without actually doing any arithmetic, binary or otherwise. The actual "addition" is done by lookupTable, and everything else is straight-up string manipulation. I wrote it with the intention of making it as instructive as possible, emphasizing the process instead of efficiency. Hope it helps.

public class BinaryArithmetic {
    static String[] lookupTable = {
        "0+0+0=00",
        "0+0+1=01",
        "0+1+0=01", 
        "0+1+1=10",
        "1+0+0=01",
        "1+0+1=10",
        "1+1+0=10",
        "1+1+1=11",
    };
    static String lookup(char b1, char b2, char c) {
        String formula = String.format("%c+%c+%c=", b1, b2, c);
        for (String s : lookupTable) {
            if (s.startsWith(formula)) {
                return s.substring(s.indexOf("=") + 1);
            }
        }
        throw new IllegalArgumentException();
    }
    static String zeroPad(String s, int length) {
        while (s.length() < length) {
            s = "0" + s;
        }
        return s;
    }   
    static String add(String s1, String s2) {
        int length = Math.max(s1.length(), s2.length());
        s1 = zeroPad(s1, length);
        s2 = zeroPad(s2, length);
        String result = "";
        char carry = '0';
        for (int i = length - 1; i >= 0; i--) {
            String columnResult = lookup(s1.charAt(i), s2.charAt(i), carry);
            result = columnResult.charAt(1) + result;
            carry = columnResult.charAt(0);
        }
        if (carry == '1') {
            result = carry + result;
        }
        return result;
    }
    public static void main(String args[]) {
        System.out.println(add("11101", "1001"));
    }
}

---

While we're at it, I might as well do multiply too.

static String multiply(String s1, String s2) {
    String result = "";
    String zeroSuffix = "";
    for (int i = s2.length() - 1; i >= 0; i--) {
        if (s2.charAt(i) == '1') {
            result = add(result, s1 + zeroSuffix);
        }
        zeroSuffix += "0";
    }
    return result;
}

Solution 2

Binary string to int:

int i = Integer.parseInt("10101011", 2);
int j = Integer.parseInt("00010", 2);

Then you can do anything you please with the two ints, eg:

i = i + j;
i = i - j;

And to get them back to a binary string:

String s = Integer.toBinaryString(i);

Solution 3

The algorithms, from wikipedia:

Addition:

The simplest arithmetic operation in binary is addition. Adding two single-digit binary numbers is relatively simple, using a form of carrying:

0 + 0 → 0
0 + 1 → 1
1 + 0 → 1
1 + 1 → 0, carry 1 (since 1 + 1 = 0 + 1 × 10 in binary)

Adding two "1" digits produces a digit "0", while 1 will have to be added to the next column.

Subtraction:

Subtraction works in much the same way:

0 − 0 → 0
0 − 1 → 1, borrow 1
1 − 0 → 1
1 − 1 → 0

Subtracting a "1" digit from a "0" digit produces the digit "1", while 1 will have to be subtracted from the next column. This is known as borrowing. The principle is the same as for carrying. When the result of a subtraction is less than 0, the least possible value of a digit, the procedure is to "borrow" the deficit divided by the radix (that is, 10/10) from the left, subtracting it from the next positional value.

Multiplication:

Multiplication in binary is similar to its decimal counterpart. Two numbers A and B can be multiplied by partial products: for each digit in B, the product of that digit in A is calculated and written on a new line, shifted leftward so that its rightmost digit lines up with the digit in B that was used. The sum of all these partial products gives the final result.

Since there are only two digits in binary, there are only two possible outcomes of each partial multiplication:

* If the digit in B is 0, the partial product is also 0
* If the digit in B is 1, the partial product is equal to A

For example, the binary numbers 1011 and 1010 are multiplied as follows:

            1 0 1 1   (A)
          × 1 0 1 0   (B)
          ---------
            0 0 0 0   ← Corresponds to a zero in B
    +     1 0 1 1     ← Corresponds to a one in B
    +   0 0 0 0
    + 1 0 1 1      
    --------------- 
    = 1 1 0 1 1 1 0

Solution 4

Working with binary arithmetic is really no different than the more familiar base 10. Let's take addition for example

                 (1)     (1)
182      182      182      182      182
845      845      845      845      845
--- +    --- +    --- +    --- +    --- +
           7       27      027     1027

So what did you do? You right-align the numbers to add, and you proceed right-to-left, adding one digit at a time, carrying over +1 to the left as necessary.

In binary, the process is exactly the same. In fact, it's even simpler because you only have 2 "digits" now, 0 and 1!

             (1)                           (1)       (1)
11101      11101      11101      11101      11101      11101      11101
 1001       1001       1001       1001       1001       1001       1001 
----- +    ----- +    ----- +    ----- +    ----- +    ----- +    ----- +
               0         10        110       0110      00110     100110

The rest of the operations work similarly too: the same process that you use for base 10, works for base 2. And again, it's actually simpler because there are only 2 "digits", 0 and 1. This simplicity is why hardware likes the binary system.

Solution 5

Convert the binary strings to Integers and then operate on the Integers, e.g.

String add(String s1, String s2) {
    int i1 = Integer.parseInt(s1);
    int i2 = Integer.parseInt(s2);
    return Integer.toBinaryString(i1 + i2);
}

View more solutions

Comments

[Tyler Treat]

Sorry, I should have noted that I need to avoid converting them to an int or long.