Add Binary

easy bit manipulation strings

Problem

Given two binary strings a and b, return their sum as a binary string.

Inputa = "1010", b = "1011"

Output"10101"

Walk both strings from the right. Each step adds two bits plus a carry; the column digit is the parity, the new carry is 1 iff the column sum ≥ 2.

a (binary)

b (binary)

def add_binary(a, b):
    i, j, carry = len(a) - 1, len(b) - 1, 0
    out = []
    while i >= 0 or j >= 0 or carry:
        s = carry
        if i >= 0: s += int(a[i]); i -= 1
        if j >= 0: s += int(b[j]); j -= 1
        out.append(str(s & 1))
        carry = s >> 1
    return ''.join(reversed(out))

function addBinary(a, b) {
  let i = a.length - 1, j = b.length - 1, carry = 0;
  const out = [];
  while (i >= 0 || j >= 0 || carry) {
    let s = carry;
    if (i >= 0) s += a.charCodeAt(i--) - 48;
    if (j >= 0) s += b.charCodeAt(j--) - 48;
    out.push(s & 1);
    carry = s >> 1;
  }
  return out.reverse().join("");
}

class Solution {
    public String addBinary(String a, String b) {
        int i = a.length() - 1, j = b.length() - 1, carry = 0;
        StringBuilder sb = new StringBuilder();
        while (i >= 0 || j >= 0 || carry > 0) {
            int s = carry;
            if (i >= 0) s += a.charAt(i--) - '0';
            if (j >= 0) s += b.charAt(j--) - '0';
            sb.append(s & 1);
            carry = s >> 1;
        }
        return sb.reverse().toString();
    }
}

string addBinary(string a, string b) {
    int i = (int) a.size() - 1, j = (int) b.size() - 1, carry = 0;
    string out;
    while (i >= 0 || j >= 0 || carry) {
        int s = carry;
        if (i >= 0) s += a[i--] - '0';
        if (j >= 0) s += b[j--] - '0';
        out.push_back('0' + (s & 1));
        carry = s >> 1;
    }
    reverse(out.begin(), out.end());
    return out;
}

Explanation

This is just grade-school addition, but in base 2. We add the two binary strings column by column from the right, carrying over whenever a column adds up to 2 or more — exactly like adding decimal numbers, only the "ten" becomes a "two".

Two pointers i and j start at the last characters of a and b. The loop runs while either pointer still has digits or there's a leftover carry, which neatly handles the case where the sum is longer than both inputs.

At each step we add the current bits plus the carry into s. The digit we write is s & 1 (the low bit, i.e. s mod 2), and the new carry is s >> 1 (s divided by 2). We collect digits and reverse at the end since we built the result right-to-left.

Example: a = "1010", b = "1011". Rightmost column 0 + 1 = 1 (write 1). Next 1 + 1 = 2 → write 0, carry 1. Then 0 + 0 + 1 = 1. Then 1 + 1 = 2 → write 0, carry 1. The leftover carry writes a final 1, giving "10101".

Time: O(max(|a|, |b|)) Space: O(max(|a|, |b|))