Add Binary

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

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.

import java.math.BigInteger;

class Solution {
    public String binaryAddition(String s1, String s2) {
        BigInteger first = new BigInteger(s1, 2);
        BigInteger second = new BigInteger(s2, 2);
        BigInteger zeroValue = new BigInteger("0", 2);
        BigInteger carryValue, sum;
        while (second.compareTo(zeroValue) != 0) {
            sum = first.xor(second);
            carryValue = first.and(second).shiftLeft(1);
            first = sum;
            second = carryValue;
        }
        return first.toString(2);
    }
}

The "Add Binary" solution in Java involves using the BigInteger class to handle binary number operations effectively. This approach provides an efficient way to add two binary strings without worrying about overflow or manually managing binary operations at the character level.

Follow these steps to understand how the provided Java solution works for adding two binary strings:

1. Initialize two BigInteger instances from the input strings s1 and s2 by specifying a radix of 2, converting the binary string inputs into their numeric representations.
2. Define a BigInteger instance for the zero value, useful for the comparison to determine when the addition loop should stop.
3. Use a while loop to perform the addition until the second number becomes zero. Inside the loop:
   • Calculate the sum of first and second using the XOR operation, which adds the two numbers without carrying bits.
   • Compute the carryValue using the AND operation, then shift the result left by one bit to position the carry correctly.
   • Update first with the sum and second with carryValue for the next iteration of the loop.
4. Once the loop completes, convert first back to a binary string using the toString() method with radix 2, and return this result.

This method accurately solves the addition of two binary numbers leveraging the capabilities of the BigInteger class to handle large numbers and avoid direct bit manipulation challenges seen in more manual approaches.

// Function to invert a string in its place
void invertString(char *str) {
    int length = strlen(str);
    for (int index = 0; index < length / 2; index++) {
        char temp = str[index];
        str[index] = str[length - 1 - index];
        str[length - 1 - index] = temp;
    }
}

// Function to perform binary addition and return the resulting binary string
char *binaryAddition(const char *s1, const char *s2) {
    int lengthS1 = strlen(s1);
    int lengthS2 = strlen(s2);
    int maxLength = lengthS1 > lengthS2 ? lengthS1 : lengthS2;

    // Allocate space for the sum, perhaps one more than the length for carry
    char *sumResult = malloc(maxLength + 2);
    if (!sumResult) return NULL;
    sumResult[maxLength + 1] = '\0';

    // Duplicate and invert the strings for easier LSB to MSB calculations
    char *copy1 = strdup(s1);
    char *copy2 = strdup(s2);
    if (!copy1 || !copy2) {
        free(sumResult);
        free(copy1);
        free(copy2);
        return NULL;
    }
    invertString(copy1);
    invertString(copy2);

    int carryOver = 0;
    for (int pos = 0; pos <= maxLength; pos++) {
        int bit1 = pos < lengthS1 ? copy1[pos] - '0' : 0;
        int bit2 = pos < lengthS2 ? copy2[pos] - '0' : 0;

        // Calculate the sum bit by bit
        int sum = bit1 ^ bit2 ^ carryOver;
        carryOver = (bit1 & bit2) | (carryOver & (bit1 ^ bit2));

        sumResult[pos] = sum + '0';
    }

    // Handle carry over for the most significant bit
    if (carryOver) {
        sumResult[maxLength] = carryOver + '0';
    }

    // Reverse the completed result to the original bit order
    invertString(sumResult);

    // Eliminate leading '0' if it's not the only character
    if (sumResult[0] == '0' && sumResult[1] != '\0') {
        memmove(sumResult, sumResult + 1, strlen(sumResult));
    }

    free(copy1);
    free(copy2);
    return sumResult;
}

The code provided is a C implementation for adding two binary strings and returning the result as a new binary string. Here’s how this solution is organized and executed:

• String Inversion Function: The invertString function takes a string and reverses it in-place. This reversal aids in easier least significant bit (LSB) to most significant bit (MSB) calculation by allowing operations from left to right as string indices increase.

• Binary Addition Function:

  • Two input binary strings s1 and s2 are initially measured to determine their lengths. Additional memory is allocated for the result with an extra space for a possible carry bit.
  • Both binary strings are duplicated and reversed to facilitate easy addition from LSB to MSB.
  • An iteration through the length of the longer string performs the addition. For each position, it computes the bit result using XOR operations between corresponding bits of s1, s2 and the carry from the previous computation. The carry for the next iteration is updated based on the current bits.
  • After processing all bits, any resultant carry is considered.
  • Following the addition, the resultant binary string is reversed back to its original order.
  • If there's a leading '0' (and it's not the only character), it's removed to properly format the binary result.
  • Memory allocated for the temporary strings is freed before returning the result.

This implementation handles the addition of binary numbers of differing lengths and ensures optimal memory management by allocating only as much space as needed and freeing up resources appropriately. The solution ensures the result is correct, dealing with the nuances of binary calculation such as carry and bit overflow.

var binarySum = function (binary1, binary2) {
    let num1 = BigInt(`0b`{binary1}`);
    let num2 = BigInt(`0b`{binary2}`);
    let none = BigInt(0);
    while (num2 != none) {
        let sum = num1 ^ num2;
        let carryOver = (num1 & num2) << BigInt(1);
        num1 = sum;
        num2 = carryOver;
    }
    return num1.toString(2);
};

This solution pertains to the problem of adding two binary numbers using JavaScript. The function binarySum is defined to take two strings, binary1 and binary2, as input. These strings represent binary numbers.

• Start by converting both binary string inputs to BigInt using JavaScript's BigInt type. This is crucial as binary numbers can be large, and their operations can exceed the safe limits for standard integers.

• Initialize the loop condition with num2 not equal to zero. The purpose of the loop is to simulate binary addition where sum represents the result of bitwise XOR between num1 and num2, effectively adding the two numbers without carrying over bits.

• carryOver computes the bits that will be carried over in the next iteration of the loop. It involves a bitwise AND operation between num1 and num2 followed by a left shift operation to carry the bits over to their correct positions.

• In each iteration, update num1 with the new sum and update num2 with the new carry over value. This repeats until there is nothing left to carry over (num2 becomes zero).

• Once the loop completes, num1 contains the result of the binary addition in BigInt form. Convert it back to a binary string with toString(2) and return the result.

This approach efficiently handles the binary addition, leveraging bitwise operations combined with loop constructs to manage carry over bits, all within the powerful and appropriately large number storage provided by BigInt.

class Solution:
    def combineBinary(self, string1, string2) -> str:
        binary1, binary2 = int(string1, 2), int(string2, 2)
        while binary2:
            result = binary1 ^ binary2
            carry = (binary1 & binary2) << 1
            binary1, binary2 = result, carry
        return bin(binary1)[2:]

This Python solution addresses the challenge of adding two binary strings and returning the sum as a binary string. The approach leverages bitwise operations to simulate the binary addition:

• Convert both binary string inputs to integers using Python's base conversion.
• Use a loop to continuously apply the bitwise XOR (^) to get the sum without carry and bitwise AND (&) followed by a left shift (<<) to calculate the carry.
• Update the sum and carry until the carry is zero.
• Finally, convert the integer result back to a binary string, slicing off the '0b' prefix to match the required format.

This method efficiently mimics the behavior of a full-adder circuit using bitwise operations, offering a clear and direct approach to binary string addition in Python.