public String addBinary(String a, String b) {

return addBinary(a, b, a.length()-1, b.length()-1, 0) ;

}

private String addBinary(String a, String b, int i, int j, int carry) {

if (i < 0 && j < 0) return (carry == 0) ? "" : "1";

int sum = carry;

if (i >= 0 && a.charAt(i) == '1') sum++;

if (j >= 0 && b.charAt(j) == '1') sum++;

return addBinary(a, b, i-1, j-1, (sum < 2) ? 0 : 1) + ((sum%2 == 0) ? "0" : "1");

}

public String addBinary2(String a, String b) {

StringBuilder sb = new StringBuilder();

addBinary(a, b, a.length()-1, b.length()-1, 0, sb) ;

return sb.toString();

}

private void addBinary(String a, String b, int i, int j, int carry, StringBuilder sb) {

if (i < 0 && j < 0) {

sb.append((carry == 0) ? "" : "1");

return;

}

int sum = carry;

if (i >= 0 && a.charAt(i) == '1') sum++;

if (j >= 0 && b.charAt(j) == '1') sum++;

addBinary(a, b, i-1, j-1, (sum < 2) ? 0 : 1, sb);

sb.append((sum%2 == 0) ? '0' : '1');

}

public String addBinary3(String a, String b) {

StringBuilder sb = new StringBuilder();

int carry = 0;

int i = a.length()-1;

int j = b.length()-1;

while (i >= 0 && j >= 0) {

int sum = carry;

if (a.charAt(i) == '1') sum++;

if (b.charAt(j) == '1') sum++;

carry = (sum < 2) ? 0 : 1;

sb.insert(0, (sum%2 == 0) ? '0' : '1');

i--;

j--;

}

while (i >= 0) {

int sum = carry;

if (a.charAt(i) == '1') sum++;

carry = (sum < 2) ? 0 : 1;

sb.insert(0, (sum%2 == 0) ? '0' : '1');

i--;

}

while (j >= 0) {

int sum = carry;

if (b.charAt(j) == '1') sum++;

carry = (sum < 2) ? 0 : 1;

sb.insert(0, (sum%2 == 0) ? '0' : '1');

j--;

}

if (carry == 1) sb.insert(0, '1');

return sb.toString();

}

public String addBinary4(String a, String b) {

char[] intToChar = new char[]{'0', '1'};

int len = Math.max(a.length(), b.length());

char[] res = new char[len + 1];

int carry = 0;

int s = len;

int i = a.length() - 1;

int j = b.length() - 1;

while (i >= 0 && j >= 0) {

int sum = charToInt(a.charAt(i--)) + charToInt(b.charAt(j--)) + carry;

carry = sum >> 1;

res[s--] = intToChar[sum & 1];

}

while (i >= 0) {

int sum = charToInt(a.charAt(i--)) + carry;

carry = sum >> 1;

res[s--] = intToChar[sum & 1];

}

while (j >= 0) {

int sum = charToInt(b.charAt(j--)) + carry;

carry = sum >> 1;

res[s--] = intToChar[sum & 1];

}

res[0] = intToChar[carry];

return res[0] == '0' ? (new String(res)).substring(1) : new String(res);

}

private int charToInt(char c) {

return c - '0';

}