Add two numbers [Bit manipulation]

67.Add Binary

Math

String

Bit Manipulation

Problem Statement:

Given two binary strings a and b, return their sum as a binary string. The strings contain only '0' or '1' characters.

Example:

Input:

a = "11"
b = "1"

→

Output:

"100"

11 + 1 = 100 in binary (3 + 1 = 4 in decimal)

Binary Addition Rules:

1. 0 + 0 = 0 (sum = 0, carry = 0)
2. 0 + 1 = 1 (sum = 1, carry = 0)
3. 1 + 1 = 10 (sum = 0, carry = 1)
4. 1 + 1 + 1 = 11 (sum = 1, carry = 1)

Algorithm:

1. Start from rightmost digits (least significant bits)
2. Keep track of carry bit
3. For each position:
   • Sum digits from both numbers and carry
   • New carry = 1 if sum is 2 or 3
   • Current digit = sum % 2
4. Append final carry if needed
5. Reverse result string

Complexity:

Time: O(max(n,m)) | Space: O(max(n,m))

Java Solution:

public String addBinary(String a, String b) {
    StringBuilder res = new StringBuilder();
    int i = a.length() - 1;
    int j = b.length() - 1;
    int carry = 0;

    while(i >= 0 || j >= 0) {
        int sum = carry;
        
        if(i >= 0) sum += a.charAt(i--) - '0';
        if(j >= 0) sum += b.charAt(j--) - '0';

        carry = sum == 2 || sum == 3 ? 1 : 0;
        res.append(sum % 2);
    }
    
    if(carry != 0) res.append(carry);
    return res.reverse().toString();
}

Python Solution:

def addBinary(self, a: str, b: str) -> str:
    result = []
    carry = 0
    i, j = len(a) - 1, len(b) - 1
    
    while i >= 0 or j >= 0 or carry:
        total = carry
        
        if i >= 0:
            total += int(a[i])
            i -= 1
        if j >= 0:
            total += int(b[j])
            j -= 1
        
        carry = 1 if total == 2 or total == 3 else 0
        result.append(str(total % 2))
    
    return ''.join(result[::-1])

C++ Solution:

string addBinary(string a, string b) {
    string result;
    int i = a.length() - 1;
    int j = b.length() - 1;
    int carry = 0;
    
    while(i >= 0 || j >= 0 || carry) {
        int sum = carry;
        
        if(i >= 0) sum += a[i--] - '0';
        if(j >= 0) sum += b[j--] - '0';
        
        carry = (sum == 2 || sum == 3) ? 1 : 0;
        result.push_back((sum % 2) + '0');
    }
    
    reverse(result.begin(), result.end());
    return result;
}