C Program To Add Two Binary Strings

In this blog post, I will teach you to how to write a C Program to Add Two Binary Strings.

Examples,

Example 1:
Input: a = "10", b = "1"
Output: "101"


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

 

Problem Statement: Given two binary strings bStr1 and bStr2, return their sum as a binary string.

Constraints:

 1 <= bStr1.len , bStr2.len <= 104

bStr1 and bStr2 consist only of ‘0’ or ‘1’ characters.

Each string does not contain leading zeros (zeros that appear at the beginning of a number) except for the zero itself.  Example,

  • Allowed strings: “0”, “1”, “01”, “234”
  • Disallowed strings: “01” , “012” , “001”

Disclaimer: Try to solve the problem yourself first otherwise it would be not worth solving this problem.

 

C Program To Add Two Binary Strings:

 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Function to add binary strings bStr1 and bStr2
char* addBinary(char* bStr1, char* bStr2)
{
    int lenStr1 = strlen(bStr1);
    int lenStr2 = strlen(bStr2);

    int maxSize = (lenStr1 > lenStr2) ? lenStr1 : lenStr2;

    /* Allocate memory for the new
    binary string and initialize variables*/
    char* pStr = (char*)malloc((maxSize + 2) * sizeof(char));
    if(pStr != NULL)
    {
        int carry = 0;
        int i = (lenStr1 - 1), j = (lenStr2 - 1);
        int k = 0;

        // Perform binary addition
        while ((i >= 0) || (j >= 0) || carry)
        {
            int sum = carry;
            if (i >= 0)
            {
                sum += bStr1[i--] - '0';
            }
            if (j >= 0)
            {
                sum += bStr2[j--] - '0';
            }

            pStr[k++] = (sum % 2) + '0';
            carry = sum / 2;
        }

        //Insert the null terminator to the result binary string
        pStr[k] = '\0';

        // Reverse the result binary string
        int left = 0, right = k - 1;
        while (left < right)
        {
            char temp = pStr[left];
            pStr[left++] = pStr[right];
            pStr[right--] = temp;
        }
    }

    return pStr;
}

int main()
{
    char bStr1[] = "1101";
    char bStr2[] = "100";

    char* addedBString = addBinary(bStr1, bStr2);
    printf("The sum of %s and %s is: %s\n",bStr1,bStr2,addedBString);

    free(addedBString); // Deallocate the memory

    return 0;
}

Output:

The sum of 1101 and 100 is: 10001

 

Explanation of C Program to Add Two Binary Strings:

In the above C code, the addBinary() function takes two binary strings bStr1 and bStr2 as a parameter and returns their sum as a dynamically allocated binary string.

The addBinary() function calculates the length of the input strings and determines the maximum length for the dynamically allocated memory to store their sum. In further steps it performs the binary addition on bStr1 and bStr2 from right to left, considering carry if present.

Recommended Post for you: