Pasted

public static String add(String bits1, String bits2) {
    int len1 = bits1.length();
    int len2 = bits2.length();
    int max = Math.max(len1, len2);
    StringBuilder result = new StringBuilder(1 + max);
    boolean one = false;
    for (int i = 1; i <= max; i++) {
        final char c1 = len1 - i >= 0 ? bits1.charAt(len1 - i) : '0';
        final char c2 = len2 - i >= 0 ? bits2.charAt(len2 - i) : '0';
        if (('0' ^ c1) > 1 || ('0' ^ c2) > 1)
            throw new IllegalArgumentException(bits1 + " + " + bits2);
        if (c1 + c2 == 2 * '0') {
            result.append(one ? '1' : '0');
            one = false;
        } else if (c1 + c2 == '0' + '1') {
            result.append(one ? '0' : '1');
        } else if (c1 + c2 == 2 * '1') {
            result.append(one ? '1' : '0');
            one = true;
        } else
            throw new IllegalArgumentException(bits1 + " + " + bits2);
    }
    if (one)
        result.append('1');
    return result.reverse().toString();
}