My 4 MS Solution using bit manipulation


  • 0
    D

    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);
    }
    

    }


Log in to reply
 

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