Add Binary

Given two numbers in their binary representation. The two numbers is very large so that they are both represented as String. Add the two number and return the result in the same representation way.

The simplest way to solve this problem is to use Java's BigInteger:

import java.math.BigInteger;

public class AddBinary {
    public String addBinary(String a, String b) {
        BigInteger m = new BigInteger(a, 2);
        BigInteger n = new BigInteger(b, 2);
        return m.add(n).toString(2);
    }
}

But this may not be a valid solution in an interview. Another way is to performing binary operations instead of using + operator. It is also a common question. Let's think first for add two int with out +. We know that x ^ y is in fact adding two integer without carries. And we can get curries by (x & y) << 1. So (x ^ y) + ((x & y) << 1) is the same as x + y. But + is not available, so we can recursively or looply calls our plus function until the carries becames zero.

public class ImplementPlusOperator {
    public int plus(int a, int b) {
        int remain = 0;
        int carry = 0;
        do {
            remain = a ^ b;
            carry = (a & b) << 1;
            a = remain;
            b = carry;
        } while (carry != 0)
        return remain;
    }
}

So the same to our binary string, we just need to implement our own XOR, AND and left shift function for the string.

public class Solution {
    private String xorBinary(String a, String b) {
        String longer;
        String shorter;

        if (a.length() >= b.length()) {
            longer = a;
            shorter = b;
        } else {
            longer = b;
            shorter = a;
        }
        char[] result = longer.toCharArray();
        int delta = longer.length() - shorter.length();
        for (int i = 0; i < shorter.length(); i++) {
            char ch = shorter.charAt(i);
            if (ch == '1') {
                if (result[delta + i] == '1') result[delta + i] = '0';
                else result[delta + i] = '1';
            }
        }
        return String.valueOf(result);
    }

    private String andBinary(String a, String b) {
        String longer;
        String shorter;

        if (a.length() >= b.length()) {
            longer = a;
            shorter = b;
        } else {
            longer = b;
            shorter = a;
        }
        char[] result = new char[longer.length()];
        Arrays.fill(result, '0');
        int delta = longer.length() - shorter.length();
        for (int i = 0; i < shorter.length(); i++) {
            char ch = shorter.charAt(i);
            if (ch == '1' && longer.charAt(delta + i) == '1') result[delta + i] = '1';
        }
        return String.valueOf(result);
    }

    private String leftShift(String s) {
        s = s + "0";
        int first1 = s.indexOf('1');
        return s.substring(first1);
    }

    private boolean isZero(String s) {
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '1') return false;
        }
        return true;
    }

    public String addBinary(String a, String b) {
        String carry = andBinary(a, b);
        String remain = xorBinary(a, b);
        if (!isZero(carry)) {
            return addBinary(remain, leftShift(carry));
        }
        return remain;
    }