Geek Answers Handbook

Algorithm for binary arithmetic in Java

On paper, binary arithmetic is simple, but as a novice programmer, it's hard for me to come up with algorithms for adding, subtracting, multiplying, and dividing binary numbers.

I have two binary numbers stored as strings, suppose all leading zeros have been removed. How can I perform these operations on two numbers?

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

+5
source share
6 answers

The following code implements binary addition without actually performing arithmetic, binary, or others. The actual “add” is done lookupTable, and everything else is straightforward string manipulation. I wrote this in order to make it as instructive as possible, emphasizing the process, not the effectiveness. Hope this 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 do this, I could also do multiply.

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;
}
+4
source

Binary string for int:

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

Then you can do anything with two ints, for example:

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

And return them to the binary string:

String s = Integer.toBinaryString(i);
+11
source

, :

:

- . , :

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

"1" "0", 1 .

:

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

"1" "0", "1" , 1 . . . 0, , "" ( 10/10) , .

. A B : B, , , B . .

, :

* 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

, 1011 1010 :

            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
+5

10. , ,

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

? , , , +1 .

. , , 2 "", 0 1!

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

: , 10, 2. , , 2 "", 0 1. - .

+2

, ,

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

BitSet .

0

More articles:


All Articles