C Program to Add 2 Binary Strings
Given two Binary Strings, we have to return their sum in binary form.
Approach: We will start from the last of both strings and add it according to binary addition, if we get any carry we will add it to the next digit.
Input:
11 + 11
Output:
110
C
// C Program to Add 2 Binary Strings // and Print their Binary Sum #include <stdio.h> #include <string.h> // Function to add two Binary Strings void sum( char b1[], char b2[], int l1, int l2) { int carry = 0, temp, num1, num2, i; char result[100]; result[l1 + 1] = '\0' ; // This loop will add Both Strings till // second have characters in it. while (l2 > 0) { num1 = b1[l1 - 1] - '0' ; num2 = b2[l2 - 1] - '0' ; temp = num1 + num2 + carry; if (temp >= 2) { carry = 1; temp = temp % 2; } result[l1] = temp + '0' ; l1--; l2--; } // This loop will add leftover // characters of first Strings. while (l1 - 1 >= 0) { temp = b1[l1 - 1] + carry - '0' ; if (temp >= 2) { carry = 1; temp = temp % 2; } result[l1] = temp + '0' ; l1--; } // Add last carry to result string if (carry) { result[0] = '1' ; } else { // if there is no carry then we will shift // each character by one place in left side. for (i = 0; i < strlen (result) - 1; i++) { result[i] = result[i + 1]; } result[ strlen (result) - 1] = '\0' ; } // printing result printf ( "%s + %s = %s\n" , b1, b2, result); } // Driver code int main() { char b1[100] = "11" , b2[100] = "11" ; int l1, l2; printf ( "Enter binary number 1: " ); printf ( "%s \n" , b1); printf ( "Enter binary number 2: " ); printf ( "%s \n" , b2); l1 = strlen (b1); l2 = strlen (b2); // calling function to add strings if (l1 > l2) { sum(b1, b2, l1, l2); } else { sum(b2, b1, l2, l1); } return 0; } |
Enter binary number 1: 11 Enter binary number 2: 11 11 + 11 = 110
The time complexity is O(n), where n is the length of the longer binary string.
The auxiliary space is O(n), where n is the length of the longer binary string.
Method: Using a while loop
C
#include <stdio.h> int main() { long binary1=10000, binary2=10000; int i = 0, remainder = 0, sum[20]; while (binary1 != 0 || binary2 != 0) { sum[i++] =(binary1 % 10 + binary2 % 10 + remainder) % 2; remainder =(binary1 % 10 + binary2 % 10 + remainder) / 2; binary1 = binary1 / 10; binary2 = binary2 / 10; } if (remainder != 0) sum[i++] = remainder; --i; printf ( "Sum of two binary numbers: " ); while (i >= 0) printf ( "%d" , sum[i--]); return 0; } |
Sum of two binary numbers: 100000
The time complexity is O(log n)
The auxiliary space is also O(log n)
Method 3: Bitwise Addition
This approach uses the concept of binary addition to add two binary strings a and b. The steps are as follows:
- Calculate the lengths of both strings a and b using the strlen() function.
- Initialize a variable carry to 0, and two variables i and j to the lengths of the strings minus one.
- Initialize a variable maxLen to the maximum length of the two strings, and allocate memory for a result string of size maxLen + 1 using the malloc() function. Set the last element of the result string to the null character \0.
- While either i or j is greater than or equal to zero, do the following:
- Initialize a variable sum to carry.
- If i is greater than or equal to zero, add the numeric value of the i-th character of a (converted from ASCII to integer using the – ‘0’ expression) to sum and decrement i.
- If j is greater than or equal to zero, add the numeric value of the j-th character of b (converted from ASCII to integer using the – ‘0’ expression) to sum and decrement j.
- Divide sum by 2 using the right shift operator >>, and store the result in carry.
- Set the maxLen-th character of the result string (converted to ASCII using the +’0′ expression) to the least significant bit of sum (obtained using the bitwise AND operator & with 1), and decrement maxLen.
- If there is a final carry after the previous loop, do the following:
- Reallocate memory for the result string to accommodate one extra character using the realloc() function.
- Shift the result string to the right by one using the memmove() function.
- Set the leftmost character of the result string to ‘1’.
- Return the result string.
- Free the memory allocated for the result string using the free() function.
Below is the implementation of the above approach:
C
#include <stdio.h> #include <string.h> char *addBinary( char *a, char *b) { int len1 = strlen (a); int len2 = strlen (b); int carry = 0, i = len1-1, j = len2-1; int maxLen = len1 > len2 ? len1 : len2; char *result = ( char *) malloc ((maxLen + 1) * sizeof ( char )); // allocate memory for result string result[maxLen] = '\0' ; // add binary digits from right to left while (i >= 0 || j >= 0) { int sum = carry; if (i >= 0) sum += a[i--] - '0' ; if (j >= 0) sum += b[j--] - '0' ; carry = sum >> 1; // carry is 1 if sum is 2 or greater, 0 otherwise result[--maxLen] = (sum & 1) + '0' ; // set the rightmost bit of result to the sum's least significant bit } if (carry) { // if there is a final carry, prepend it to the result result = ( char *) realloc (result, ( strlen (result) + 2) * sizeof ( char )); // reallocate memory for bigger result string memmove (result + 1, result, strlen (result) + 1); // shift result string to the right by 1 result[0] = '1' ; // set the leftmost bit to 1 } return result; } int main() { char a[] = "101" ; char b[] = "1101" ; char *result = addBinary(a, b); printf ( "Sum of %s and %s is %s\n" , a, b, result); free (result); // free memory allocated for result string return 0; } |
Sum of 101 and 1101 is 10010
The time complexity of the addBinary function is O(n), where n is the length of the longer input string.
The auxiliary space complexity of the function is also O(n), where n is the length of the longer input string.
Approach: Binary Addition using Bitwise Operations
This approach uses bitwise operators to perform binary addition. It is a more efficient approach compared to the traditional method of converting the binary strings to decimal and then adding them.
Steps:
- Define a constant MAX_LEN to store the maximum length of the binary strings.
- Declare a function addBinary that takes two binary strings as input and returns the resultant binary string.
- Initialize a static character array result of size MAX_LEN to store the resultant binary string.
- Determine the lengths of the binary strings a and b.
- Initialize the carry to 0 and index variables i, j, and k to the lengths of the binary strings a, b, and result minus 1, respectively.
- Loop through the binary strings from right to left until all digits have been added and the carry is 0.
- Compute the sum of the digits and the carry, and add the sum modulo 2 to the result array at index k.
- Update the carry to the sum divided by 2.
- Reverse the result array to get the correct order of digits.
- In the main function, prompt the user to input the binary strings a and b.
- Call the addBinary function to add the binary strings a and b.
- Display the sum of the binary strings to the user.
C
#include <stdio.h> #include <string.h> #define MAX_LEN 100 // Function to add two binary strings char * addBinary( char * a, char * b) { static char result[MAX_LEN]; // Resultant binary string int len_a = strlen (a); int len_b = strlen (b); int carry = 0; // Initialize carry to 0 int i = len_a - 1, j = len_b - 1, k = 0; // Index variables // Loop through the binary strings from right to left while (i >= 0 || j >= 0 || carry == 1) { int sum = carry; if (i >= 0) sum += a[i--] - '0' ; // Convert character to integer if (j >= 0) sum += b[j--] - '0' ; // Convert character to integer result[k++] = (sum % 2) + '0' ; // Convert integer to character carry = sum / 2; } // Reverse the resultant binary string int len_result = strlen (result); for ( int i = 0; i < len_result / 2; i++) { char temp = result[i]; result[i] = result[len_result - i - 1]; result[len_result - i - 1] = temp; } return result; } int main() { char a[MAX_LEN], b[MAX_LEN]; strcpy (a, "11" ); strcpy (b, "11" ); printf ( "The sum of %s and %s is %s\n" , a, b, addBinary(a, b)); return 0; } |
The sum of 11 and 11 is 110
Time Complexity: O(n), where n is the length of the binary strings.
Auxiliary Space: O(n), where n is the length of the binary strings.
Contact Us