How to add two large binary strings? Is there any inbuilt functions in java or do i have to do it manually?

Question

https://leetcode.com/problems/add-binary/

I tried to convert the string into integers using String.parseInt(stringname,2) and add the numbers, then i tried to return Integer.toBinaryString(sum).but for large strings i am getting errors.

class Solution {
    public String addBinary(String a, String b) {
        int n1=Integer.parseInt(a,2);
        int n2=Integer.parseInt(b,2);
        int n=n1+n2;
        return Integer.toBinaryString(n);
    }
}

Answer 1

Here is an example.

String addBinary(String a, String b) {
    StringBuilder s = new StringBuilder();
    char A[] = a.toCharArray(), g;
    char B[] = b.toCharArray(), h;
    boolean r = false;
    int p, q, n = Math.max(p = A.length, q = B.length);
    for (int i = 0; i < n; i++) {
        g = '0';
        h = '0';
        if (i < p) g = A[p - 1 - i];
        if (i < q) h = B[q - 1 - i];
        if (g == '1' && h == '1')
            if (r) s.insert(0, '1');
            else {
                s.insert(0, '0');
                r = true;
            }
        else if (g == '0' && h == '0')
            if (!r) s.insert(0, '0');
            else {
                s.insert(0, '1');
                r = false;
            }
        else s.insert(0, r ? '0' : '1');
        if (i + 1 == n && r) s.insert(0, '1');
    }
    return s.toString();
}

Answer 2

I would just use your approach using BigInteger. I'm using Random to just generate values that are randomly signed for demonstration.

Random r = new Random();
for (int i = 0; i < 10; i++) {
    String a = (r.nextBoolean()?"": "-")+Integer.toBinaryString(r.nextInt(100));  
    String b = (r.nextBoolean()?"": "-")+Integer.toBinaryString(r.nextInt(100));
    String result = addBinary(a,b); 
    System.out.printf("%10s + %10s = %s%n",a,b,result);
}

prints something like

    -11000 +    -101111 = -1000111
    101011 +       -101 = 100110
        -0 +        110 = 110
  -1001101 +       -101 = -1010010
     -1000 +      10100 = 1100
   -111011 +   -1001111 = -10001010
    110011 +     -10100 = 11111
    110010 +    1001011 = 1111101
     10111 +    1010111 = 1101110
   -111001 +     101100 = -1101

The modified method

public static String addBinary(String a, String b) {
    BigInteger ba = new BigInteger(a,2);
    BigInteger bb = new BigInteger(b,2);
    return ba.add(bb).toString(2);
}

Since BigInteger has arbitrary precision, negative binary numbers are shown simply as negative and not in 2's complement form.