Add Binary

2 min readUpdated 12 May 2025

Problem Statement

In this computational problem, you are given two binary strings labeled a and b. The task is to compute their sum and return the result as a binary string. Binary strings are representations of numbers using only two digits, 0 and 1. When these binary strings are added, they follow the same rules as decimal addition, but the summing is based on the binary number system, which has only two base symbols (binary digits), instead of ten like in the usual decimal system.

Examples

Example 1

Input:

EXAMPLE_ENTITY

a = "11", b = "1"

Output:

EXAMPLE_ENTITY

"100"

Example 2

Input:

EXAMPLE_ENTITY

a = "1010", b = "1011"

Output:

EXAMPLE_ENTITY

"10101"

Constraints

1 <= a.length, b.length <= 104
a and b consist only of '0' or '1' characters.
Each string does not contain leading zeros except for the zero itself.

Approach and Intuition

When dealing with the addition of two binary strings, the solution closely mimics the process of addition that we perform with decimal numbers, albeit simplified due to there being only two numerals. Let's decompose our approach:

Reverse Both Strings: Initiate by reversing both strings to simplify the addition from least significant bit to most, similar to how we perform hand-calculated additions from right to left.
Initialize Variables: Set up an index counter and a carry variable. The index will help manage our current position in the binary strings during addition from the rightmost side, and the carry will hold any overflow that occurs beyond one (since 1+1=10 in binary).
Addition Process: As we iterate over the reversed strings, we perform bit-by-bit addition. If a position only exists in one string (because the strings are of unequal length), we handle it separately by considering the non-existent bit as 0.
- For each pair of bits, including the carry:
  - Sum the bits including the carried over value.
  - If the sum is 2 (binary 10), the result bit becomes 0 and carry becomes 1.
  - If the sum is 3 (binary 11), the result bit becomes 1 and carry remains 1.
  - In cases of sum being 0 or 1, simply append the sum to the result and carry over 0 if necessary.
Final Carry: Post iteration, if there is a remaining carry, append this to the result string.
Reverse the Result: Given that we've been constructing the result by adding smallest position values first, the final result string is reversed before being returned.

This step-by-step method works efficiently within the constraints provided and ensures that each bit is considered. The absence of leading zeros in the input strings simplifies the process, excluding the need for handling ambiguous cases of multiple leading zeros in the binary calculation.

Solutions

CPP
class LargeInteger {
private:
    string binValue;
    
    // Helper function for aligning lengths of two binary strings
    static void alignStrings(string& s1, string& s2) {
        int lengthDiff = s1.length() - s2.length();
        if (lengthDiff > 0)
            s2.insert(0, lengthDiff, '0');
        else
            s1.insert(0, -lengthDiff, '0');
    }
    
    // Helper function to clean up leading zeros from the binary string
    void trimLeadingZeros() {
        size_t firstNonZeroIndex = binValue.find_first_not_of('0');
        if (firstNonZeroIndex != string::npos) {
            binValue.erase(0, firstNonZeroIndex);
        } else {
            binValue = "0";
        }
    }
    
public:
    LargeInteger() : binValue("0") {}
    
    // Constructs the number from a binary-encoded string
    LargeInteger(const string& bin) : binValue(bin) { trimLeadingZeros(); }
    
    // Binary XOR operation
    LargeInteger operator^(const LargeInteger& other) const {
        string left = binValue;
        string right = other.binValue;
        alignStrings(left, right);
        string xorResult;
        for (size_t i = 0; i < left.size(); i++) {
            char resChar = (left[i] == right[i] ? '0' : '1');
            xorResult.push_back(resChar);
        }
        return LargeInteger(xorResult);
    }
    
    // Binary AND operation
    LargeInteger operator&(const LargeInteger& other) const {
        string left = binValue;
        string right = other.binValue;
        alignStrings(left, right);
        string andResult;
        for (size_t i = 0; i < left.size(); i++) {
            char resChar = (left[i] == '1' && right[i] == '1' ? '1' : '0');
            andResult.push_back(resChar);
        }
        return LargeInteger(andResult);
    }
    
    // Left bit shift operation
    LargeInteger operator<<(int numShifts) const {
        string shifted = binValue;
        shifted.append(numShifts, '0');
        return LargeInteger(shifted);
    }
    
    // Checks if the number is zero
    bool isZero() const {
        return binValue == string(binValue.length(), '0');
    }
    
    // Accessor function for binary data
    string getBinValue() const { return binValue; }
};
    
class Solution {
public:
    // Adds two binary strings
    string addBinary(string a, string b) {
        LargeInteger num1(a);
        LargeInteger num2(b);
        LargeInteger sum, carry;
    
        while (!num2.isZero()) {
            sum = num1 ^ num2;
            carry = (num1 & num2) << 1;
            num1 = sum;
            num2 = carry;
        }
        return num1.getBinValue();
    }
};
Powered by Vultr AgentBeta

This solution outlines a system for performing binary addition using two main classes: LargeInteger and Solution.

The LargeInteger class stores binary numbers as strings and offers several operations fundamental to binary arithmetic.
Operations supported by LargeInteger include:
- XOR (^): computes the bitwise XOR of two binary numbers. This operation is used in binary addition to determine sum bits without carry.
- AND (&): computes the bitwise AND of two binary numbers. This operation identifies bits where carry is generated.
- Left Bit Shift (<<): shifts a binary number to the left by a specified number of positions, effectively multiplying the number by powers of two. This operation is used for carry manipulation in binary addition.
- Additional methods include string manipulations such as aligning string lengths and trimming leading zeros, crucial for maintaining proper binary number formats and efficient calculations.
The Solution class includes the method addBinary(string a, string b) which uses an algorithm similar to elementary binary addition:
1. Initialize two LargeInteger objects, num1 and num2, from input binary strings a and b.
2. Iterate and compute the sum and carry until there's no carry left:
  - Calculate sum as the XOR of num1 and num2.
  - Determine carry from the AND of num1 and num2, then left shift the result to align carry bits for the next addition.
  - Update num1 to the current sum and num2 to the current carry.
3. Return the binary string representation of num1 once num2 is zero (indicating no further carry exists). The result is the final added value in binary form.

This approach efficiently handles binary addition, cleanly separating the arithmetic logic using class methods and leveraging bit manipulation techniques. This is ideal for scenarios involving large binary numbers or programming environments supporting high-level bit manipulation operations.

More to Explore

Tech Talk: Running a Self-Improving AI Agent with Hermes on Vultr

Tech Talk: Implementing Fine-Grained Access Control with Vultr IAM

Tech Talk: Getting Started with Vultr IAM

Tech Talk: Simplifying Zero-Trust Networking with NetBird on Vultr Marketplace

0 Comments

Start the conversation

Be the first to comment and share your perspective with the community.

Add Binary

2 min readUpdated 12 May 2025

Problem Statement

Examples

Example 1

Input:

EXAMPLE_ENTITY

a = "11", b = "1"

Output:

EXAMPLE_ENTITY

"100"

Example 2

Input:

EXAMPLE_ENTITY

a = "1010", b = "1011"

Output:

EXAMPLE_ENTITY

"10101"

Constraints

1 <= a.length, b.length <= 104
a and b consist only of '0' or '1' characters.
Each string does not contain leading zeros except for the zero itself.

Approach and Intuition

Reverse Both Strings: Initiate by reversing both strings to simplify the addition from least significant bit to most, similar to how we perform hand-calculated additions from right to left.
Initialize Variables: Set up an index counter and a carry variable. The index will help manage our current position in the binary strings during addition from the rightmost side, and the carry will hold any overflow that occurs beyond one (since 1+1=10 in binary).
Addition Process: As we iterate over the reversed strings, we perform bit-by-bit addition. If a position only exists in one string (because the strings are of unequal length), we handle it separately by considering the non-existent bit as 0.
- For each pair of bits, including the carry:
  - Sum the bits including the carried over value.
  - If the sum is 2 (binary 10), the result bit becomes 0 and carry becomes 1.
  - If the sum is 3 (binary 11), the result bit becomes 1 and carry remains 1.
  - In cases of sum being 0 or 1, simply append the sum to the result and carry over 0 if necessary.
Final Carry: Post iteration, if there is a remaining carry, append this to the result string.
Reverse the Result: Given that we've been constructing the result by adding smallest position values first, the final result string is reversed before being returned.

Solutions

CPP
class LargeInteger {
private:
    string binValue;
    
    // Helper function for aligning lengths of two binary strings
    static void alignStrings(string& s1, string& s2) {
        int lengthDiff = s1.length() - s2.length();
        if (lengthDiff > 0)
            s2.insert(0, lengthDiff, '0');
        else
            s1.insert(0, -lengthDiff, '0');
    }
    
    // Helper function to clean up leading zeros from the binary string
    void trimLeadingZeros() {
        size_t firstNonZeroIndex = binValue.find_first_not_of('0');
        if (firstNonZeroIndex != string::npos) {
            binValue.erase(0, firstNonZeroIndex);
        } else {
            binValue = "0";
        }
    }
    
public:
    LargeInteger() : binValue("0") {}
    
    // Constructs the number from a binary-encoded string
    LargeInteger(const string& bin) : binValue(bin) { trimLeadingZeros(); }
    
    // Binary XOR operation
    LargeInteger operator^(const LargeInteger& other) const {
        string left = binValue;
        string right = other.binValue;
        alignStrings(left, right);
        string xorResult;
        for (size_t i = 0; i < left.size(); i++) {
            char resChar = (left[i] == right[i] ? '0' : '1');
            xorResult.push_back(resChar);
        }
        return LargeInteger(xorResult);
    }
    
    // Binary AND operation
    LargeInteger operator&(const LargeInteger& other) const {
        string left = binValue;
        string right = other.binValue;
        alignStrings(left, right);
        string andResult;
        for (size_t i = 0; i < left.size(); i++) {
            char resChar = (left[i] == '1' && right[i] == '1' ? '1' : '0');
            andResult.push_back(resChar);
        }
        return LargeInteger(andResult);
    }
    
    // Left bit shift operation
    LargeInteger operator<<(int numShifts) const {
        string shifted = binValue;
        shifted.append(numShifts, '0');
        return LargeInteger(shifted);
    }
    
    // Checks if the number is zero
    bool isZero() const {
        return binValue == string(binValue.length(), '0');
    }
    
    // Accessor function for binary data
    string getBinValue() const { return binValue; }
};
    
class Solution {
public:
    // Adds two binary strings
    string addBinary(string a, string b) {
        LargeInteger num1(a);
        LargeInteger num2(b);
        LargeInteger sum, carry;
    
        while (!num2.isZero()) {
            sum = num1 ^ num2;
            carry = (num1 & num2) << 1;
            num1 = sum;
            num2 = carry;
        }
        return num1.getBinValue();
    }
};
Powered by Vultr AgentBeta

This solution outlines a system for performing binary addition using two main classes: LargeInteger and Solution.

The LargeInteger class stores binary numbers as strings and offers several operations fundamental to binary arithmetic.
Operations supported by LargeInteger include:
- XOR (^): computes the bitwise XOR of two binary numbers. This operation is used in binary addition to determine sum bits without carry.
- AND (&): computes the bitwise AND of two binary numbers. This operation identifies bits where carry is generated.
- Left Bit Shift (<<): shifts a binary number to the left by a specified number of positions, effectively multiplying the number by powers of two. This operation is used for carry manipulation in binary addition.
- Additional methods include string manipulations such as aligning string lengths and trimming leading zeros, crucial for maintaining proper binary number formats and efficient calculations.
The Solution class includes the method addBinary(string a, string b) which uses an algorithm similar to elementary binary addition:
1. Initialize two LargeInteger objects, num1 and num2, from input binary strings a and b.
2. Iterate and compute the sum and carry until there's no carry left:
  - Calculate sum as the XOR of num1 and num2.
  - Determine carry from the AND of num1 and num2, then left shift the result to align carry bits for the next addition.
  - Update num1 to the current sum and num2 to the current carry.
3. Return the binary string representation of num1 once num2 is zero (indicating no further carry exists). The result is the final added value in binary form.

More to Explore

Tech Talk: Running a Self-Improving AI Agent with Hermes on Vultr

Tech Talk: Implementing Fine-Grained Access Control with Vultr IAM

Tech Talk: Getting Started with Vultr IAM

Tech Talk: Simplifying Zero-Trust Networking with NetBird on Vultr Marketplace

0 Comments

Start the conversation

Be the first to comment and share your perspective with the community.