# My 4 MS Solution using bit manipulation

• Bit to be set is calculated by XOR : number 1 ^ number 2 ^ carry bit
Carry bit is calculated as : (number1 & number 2) | (number 2 & carry) | (number 1 & carry) if all there are present. Overriden method is used if only 1 of the numbers are present which returns number & carry respectively. Here I am referring number1 as bit from string 1 at ith position and number 2 as bit from string 2 at ith position

public class Solution {
public String addBinary(String a, String b) {

``````    StringBuilder sb = new StringBuilder();
int p1 = a.length()-1;
int p2 = b.length()-1;
char carry = '0';
while (p1 >= 0 && p2 >= 0) {

sb.append(((a.charAt(p1) ^ b.charAt(p2)) ^ (carry)) - '0');
carry = getCarry(a.charAt(p1), b.charAt(p2) , carry);

p1--;
p2--;

}
while (p1 >= 0) {

sb.append((a.charAt(p1) ^ carry));
carry = getCarry(a.charAt(p1) ,carry);

p1--;

}
while (p2 >= 0) {

sb.append((b.charAt(p2) ^ carry) );
carry = getCarry(b.charAt(p2), carry);

p2--;

}
if (carry != '0') {
sb.append(carry);
}
return sb.reverse().toString();

}

private char getCarry(char a, char b, char carry) {

return (char)((a & b) | (a & carry) | (b & carry));
}

private char getCarry(char a, char b) {
return (char) (a & b);
}
``````

}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.