Skip to main content

Bit Manipulation

Add Binary Solution In C++/Java/Python/JS

Problem Description

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

Example

Input: a = "11", b = "1"
Output: "100"

Input: a = "1010", b = "1011"
Output: "10101"

Constraints

  • 1 <= a.length, b.length <= 10^4
  • a and b consist only of '0' or '1' characters.
  • Each string does not contain leading zeros except for the zero itself.
💡
Try it Yourself First
We’ve all grown up solving addition problems on paper, carrying digits and moving left. What if I told you binary addition is no different—just simpler, and even more interesting?

Optimal Approach

Intuition

Let’s go back to our childhood when we learned how to add two decimal numbers like 789 + 654. We started from the rightmost digit (units place), added both digits and carried over any extra if the sum was more than 9. For example, 9 + 4 = 13, so we wrote 3 and carried 1 to the next digit. We repeated this for every digit until we were done. The carry was a key player in that process.

Binary addition works exactly the same way, except we only have 0 and 1 instead of 0 to 9. So in binary:

  • 0 + 0 = 0 (carry 0)
  • 0 + 1 = 1 (carry 0)
  • 1 + 0 = 1 (carry 0)
  • 1 + 1 = 0 with carry 1 (since 1 + 1 = 2 in decimal, which is 10 in binary)

Let’s say we are adding binary numbers a = "1010" and b = "1011". Just like we did in school, we start from the last character of both strings (rightmost bits), add them and keep track of a carry. That’s exactly how we learned decimal addition — start from the smallest place (units) and move toward the higher places (tens, hundreds).. For instance, 0 + 1 = 1 (carry 0), next step 1 + 1 = 0 (carry 1), and so on. We continue until we finish all bits from right to left, and if any carry is left in the end, we simply add it to the front of the result.

What if the lengths of the binary strings are not equal?
Just like in decimal, we imagine extra 0s in front of the shorter number. For example, adding 789 + 56 is like imagining it as 789 + 056. In binary too, we simply treat the missing digits as 0.

Approach

Step 1: Initialize the Result String
We create an empty string called result which will store the final binary sum.

Step 2: Set Two Pointers at the End of Input Strings
We define two variables, i and j, pointing to the last character (rightmost bit) of the binary strings a and b respectively.
This helps us add bits from least significant to most significant (right to left).

Step 3: Initialize Carry to 0
We need to keep track of any carry generated during the addition of two bits.
So, we define a variable carry and initialize it to 0.

Step 4: Loop Until All Bits and Carry Are Processed
We run a loop as long as i ≥ 0, j ≥ 0, or carry > 0.
This ensures we continue processing even if one string is shorter or if there is a remaining carry.

Step 5: Extract Bits from Each String
We define two integer variables bitA and bitB and initialize both to 0.
If i ≥ 0, we extract the bit from string a by converting the character to integer: bitA = a[i] - '0'
Similarly, if j ≥ 0, we extract the bit from string b: bitB = b[j] - '0'

Step 6: Calculate Sum at Current Position
We compute the sum of the two bits and the carry:
total = bitA + bitB + carry
The value of total can be 0, 1, 2, or 3.

Step 7: Determine the Bit to Add to Result
We find the result bit by taking total % 2.
If total % 2 == 0, then the bit to add is '0'. Otherwise, the bit to add is '1'

Step 8: Add Bit to the Front of Result
We update the result by prepending the bit character to it. This ensures the final string is in correct order from most significant to least significant bit.

Step 9: Update Carry and Move Pointers
We update the carry as total / 2. Then we decrement both i and j to move to the next bits on the left.

Step 10: Return the Final Result
After the loop finishes, we return the result string which contains the binary sum of the two input strings.

Dry Run

Let's do a detailed Dry Run for the given input to understand how the function adds two binary strings step by step: Input: a = "11", b = "1"

Initialize the Result String
We start with an empty string result = "" which will hold the binary sum as we calculate it.

Initialize Two Pointers
We set i = 1 (pointing to the last character of "11") and j = 0 (pointing to the last character of "1").

Initialize Carry
Set carry = 0 initially, as we have no carry from previous addition.

First Iteration (i = 1, j = 0)

  • Extract bits:
    bitA = a[1] - '0' = '1' - '0' = 1
    bitB = b[0] - '0' = '1' - '0' = 1
  • Calculate total:
    total = bitA + bitB + carry = 1 + 1 + 0 = 2
  • Determine bit to add:
    total % 2 = 2 % 2 = 0 → bitChar = '0'
  • Update result:
    result = "0" + "" = "0"
  • Update carry:
    carry = total / 2 = 2 / 2 = 1
  • Move pointers:
    i = 0, j = -1

Second Iteration (i = 0, j = -1)

  • Extract bits:
    bitA = a[0] - '0' = '1' - '0' = 1
    bitB = j < 0, so bitB = 0
  • Calculate total:
    total = bitA + bitB + carry = 1 + 0 + 1 = 2
  • Determine bit to add:
    total % 2 = 2 % 2 = 0 → bitChar = '0'
  • Update result:
    result = "0" + "0" = "00"
  • Update carry:
    carry = total / 2 = 2 / 2 = 1
  • Move pointers:
    i = -1, j = -2

Third Iteration (i = -1, j = -2)

  • Extract bits:
    bitA = 0 (since i < 0)
    bitB = 0 (since j < 0)
  • Calculate total:
    total = bitA + bitB + carry = 0 + 0 + 1 = 1
  • Determine bit to add:
    total % 2 = 1 % 2 = 1 → bitChar = '1'
  • Update result:
    result = "1" + "00" = "100"
  • Update carry:
    carry = total / 2 = 1 / 2 = 0 (integer division)
  • Move pointers:
    i = -2, j = -3

Loop Ends
Since i < 0, j < 0, and carry == 0, the loop terminates.

Return the Final Result
The final result string is "100", which is the binary sum of "11" and "1".

Code for All Languages
C++ 
#include <iostream>      // for cin and cout
#include <string>        // for string operations
using namespace std;

class Solution {
public:
    // Function to add two binary strings and return the result as a binary string
    string addBinary(string a, string b) {

        // Step 1: Initialize an empty result string
        string result = "";

        // Step 2: Initialize two pointers at the end of the strings
        int i = a.length() - 1;
        int j = b.length() - 1;

        // Step 3: Initialize carry to 0
        int carry = 0;

        // Step 4: Loop through both strings from end to start
        while (i >= 0 || j >= 0 || carry > 0) {
            int bitA = 0;
            int bitB = 0;

            // If index i is valid, convert a[i] to integer bitA
            if (i >= 0) {
                bitA = a[i] - '0';
            }

            // If index j is valid, convert b[j] to integer bitB
            if (j >= 0) {
                bitB = b[j] - '0';
            }

            // Step 5: Calculate total sum at this position (bitA + bitB + carry)
            int total = bitA + bitB + carry;

            // Step 6: Calculate the bit to add to the result (0 or 1)
            char bitChar;
            if (total % 2 == 0) {
                bitChar = '0';
            } else {
                bitChar = '1';
            }

            // Step 7: Add the bit to the front of result string
            result = bitChar + result;

            // Step 8: Update the carry
            carry = total / 2;

            // Step 9: Move to the previous bits
            i--;
            j--;
        }

        // Step 10: Return the final binary string
        return result;
    }
};

// Driver code
int main() {
    string a, b;

    // Input two binary strings
    cin >> a >> b;

    Solution sol;

    // Call the function to add binary strings and print the result
    cout << sol.addBinary(a, b);

    return 0;
}

Java 
import java.util.Scanner;   // for input

class Solution {
    // Function to add two binary strings and return the result as a binary string
    public String addBinary(String a, String b) {

        // Step 1: Initialize an empty result string using StringBuilder for efficiency
        StringBuilder result = new StringBuilder();

        // Step 2: Initialize two pointers at the end of the strings
        int i = a.length() - 1;
        int j = b.length() - 1;

        // Step 3: Initialize carry to 0
        int carry = 0;

        // Step 4: Loop through both strings from end to start
        while (i >= 0 || j >= 0 || carry > 0) {
            int bitA = 0;
            int bitB = 0;

            // If index i is valid, convert a.charAt(i) to integer bitA
            if (i >= 0) {
                bitA = a.charAt(i) - '0';
            }

            // If index j is valid, convert b.charAt(j) to integer bitB
            if (j >= 0) {
                bitB = b.charAt(j) - '0';
            }

            // Step 5: Calculate total sum at this position (bitA + bitB + carry)
            int total = bitA + bitB + carry;

            // Step 6: Calculate the bit to add to the result (0 or 1)
            char bitChar;
            if (total % 2 == 0) {
                bitChar = '0';
            } else {
                bitChar = '1';
            }

            // Step 7: Append the bit to the result string
            result.append(bitChar);

            // Step 8: Update the carry
            carry = total / 2;

            // Step 9: Move to the previous bits
            i--;
            j--;
        }

        // Step 10: Since we built the result in reverse order, reverse it
        result.reverse();

        // Step 11: Return the final binary string
        return result.toString();
    }
}

// Main class to handle input and output
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // Input two binary strings
        String a = sc.next();
        String b = sc.next();

        Solution sol = new Solution();

        // Call the function to add binary strings and print the result
        System.out.println(sol.addBinary(a, b));
    }
}

Python 
class Solution:
    # Function to add two binary strings and return the result as a binary string
    def addBinary(self, a: str, b: str) -> str:

        # Step 1: Initialize an empty result string
        result = ""

        # Step 2: Initialize two pointers at the end of the strings
        i = len(a) - 1
        j = len(b) - 1

        # Step 3: Initialize carry to 0
        carry = 0

        # Step 4: Loop through both strings from end to start
        while i >= 0 or j >= 0 or carry > 0:
            bitA = 0
            bitB = 0

            # If index i is valid, convert a[i] to integer bitA
            if i >= 0:
                bitA = int(a[i])

            # If index j is valid, convert b[j] to integer bitB
            if j >= 0:
                bitB = int(b[j])

            # Step 5: Calculate total sum at this position (bitA + bitB + carry)
            total = bitA + bitB + carry

            # Step 6: Calculate the bit to add to the result (0 or 1)
            if total % 2 == 0:
                bitChar = '0'
            else:
                bitChar = '1'

            # Step 7: Add the bit to the front of result string
            result = bitChar + result

            # Step 8: Update the carry
            carry = total // 2

            # Step 9: Move to the previous bits
            i -= 1
            j -= 1

        # Step 10: Return the final binary string
        return result


# Driver code
if __name__ == "__main__":
    # Input two binary strings
    a = input()
    b = input()

    sol = Solution()

    # Call the function to add binary strings and print the result
    print(sol.addBinary(a, b))

Javascript 
/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function(a, b) {
    // Step 1: Initialize an empty result string
    let result = "";

    // Step 2: Initialize two pointers at the end of the strings
    let i = a.length - 1;
    let j = b.length - 1;

    // Step 3: Initialize carry to 0
    let carry = 0;

    // Step 4: Loop through both strings from end to start
    while (i >= 0 || j >= 0 || carry > 0) {
        let bitA = 0;
        let bitB = 0;

        // If index i is valid, convert a[i] to integer bitA
        if (i >= 0) {
            bitA = a[i] - '0';
        }

        // If index j is valid, convert b[j] to integer bitB
        if (j >= 0) {
            bitB = b[j] - '0';
        }

        // Step 5: Calculate total sum at this position (bitA + bitB + carry)
        let total = bitA + bitB + carry;

        // Step 6: Calculate the bit to add to the result (0 or 1)
        let bitChar;
        if (total % 2 === 0) {
            bitChar = '0';
        } else {
            bitChar = '1';
        }

        // Step 7: Add the bit to the front of result string
        result = bitChar + result;

        // Step 8: Update the carry
        carry = Math.floor(total / 2);

        // Step 9: Move to the previous bits
        i--;
        j--;
    }

    // Step 10: Return the final binary string
    return result;
};

// Driver code (for testing)
const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

// Read two binary strings from input
let inputLines = [];
rl.on('line', function(line) {
    inputLines.push(line.trim());
    if (inputLines.length === 2) {
        const a = inputLines[0];
        const b = inputLines[1];
        console.log(addBinary(a, b));
        rl.close();
    }
});

Time Complexity: O(n + m)

String Length Calculation: O(1)
Calculating the lengths of strings a and b using length() is a direct property access operation and does not depend on the string contents.
So, initializing i = a.length() - 1 and j = b.length() - 1 takes constant time.

Pointer Traversal Loop: O(max(n, m))
The loop runs while there are still bits left in either string or there’s a carry.
If n = length of string a and m = length of string b, the loop runs for max(n, m) iterations.
Each iteration does:

  • Check and extract character from string if index is valid
  • Perform character to integer conversion: bitA = a[i] - '0'
  • Sum the bits and carry: total = bitA + bitB + carry
  • Compute the result bit: total % 2, a modulo operation — O(1)
  • Update the carry: carry = total / 2, integer division — O(1)
  • Append the character at the front of the result string

Appending to the front of a string like result = bitChar + result takes O(k) time in worst-case for each iteration (as string copying is involved), where k is current length of result.
Hence, across all max(n, m) iterations, this string concatenation contributes O(n + m) in total.

Final Time Complexity: O(n + m)

  • The loop runs at most n + m times
  • Each iteration does fixed-time operations except for front-string append
  • Since we build the result one bit at a time by prepending, total copying cost is linear

Thus, overall time complexity is O(n + m)

Space Complexity: O(1)

Auxiliary Space Complexity: O(1)
This refers to the extra memory used during the computation, excluding the input and output. In this program:

  • A few fixed-size variables are used: i, j, carry, bitA, bitB, total, and bitChar.
  • All of them are simple integers or characters.
  • No dynamic memory allocation, containers like vectors or arrays, or recursive stack space are used.

Therefore, the auxiliary space used is constant and does not grow with input size, i.e., O(1).

Total Space Complexity: O(n)
This includes both auxiliary space and space required for input/output:

  • Two input strings a and b of length n and m are provided by the user.
  • A new string result is built by appending one character per iteration.
  • In the worst case, the size of result can be max(n, m) + 1, if an extra carry is present at the end (like adding 1 + 1 = 10).

Hence, the total space depends on the length of the result, which is at most O(n) where n is the maximum of the input lengths.

Similar Problems

Kth Bit is Set or Not

Given two positive integer n and k, check if the kth index bit of n is set or not.
Note: A bit is called set if it is 1. 

Set the Rightmost Unset Bit

Given a non-negative number n. The problem is to set the rightmost unset bit in the binary representation of n.