Given two bit sequences as strings, write a function to return the addition of the two sequences. Bit strings can be of different lengths also. For example, if string 1 is “1100011” and second string 2 is “10”, then the function should return “1100101”.
Since the sizes of two strings may be different, we first make the size of a smaller string equal to that of the bigger string by adding leading 0s. After making sizes the same, we one by one add bits from rightmost bit to leftmost bit. In every iteration, we need to sum 3 bits: 2 bits of 2 given strings and carry. The sum bit will be 1 if, either all of the 3 bits are set or one of them is set. So we can do XOR of all bits to find the sum bit. How to find carry – carry will be 1 if any of the two bits is set. So we can find carry by taking OR of all pairs. Following is step by step algorithm.
1. Make them equal sized by adding 0s at the beginning of smaller string.
2. Perform bit addition
…..Boolean expression for adding 3 bits a, b, c
…..Sum = a XOR b XOR c
…..Carry = (a AND b) OR ( b AND c ) OR ( c AND a )
Following is implementation of the above algorithm.
C++
#include <iostream>
using namespace std;
string addBitStrings( string first, string second );
int makeEqualLength(string &str1, string &str2)
{
int len1 = str1.size();
int len2 = str2.size();
if (len1 < len2)
{
for (int i = 0 ; i < len2 - len1 ; i++)
str1 = '0' + str1;
return len2;
}
else if (len1 > len2)
{
for (int i = 0 ; i < len1 - len2 ; i++)
str2 = '0' + str2;
}
return len1;
}
string addBitStrings( string first, string second )
{
string result;
int length = makeEqualLength(first, second);
int carry = 0;
for (int i = length-1 ; i >= 0 ; i--)
{
int firstBit = first.at(i) - '0';
int secondBit = second.at(i) - '0';
int sum = (firstBit ^ secondBit ^ carry)+'0';
result = (char)sum + result;
carry = (firstBit & secondBit) | (secondBit & carry) | (firstBit & carry);
}
if (carry)
result = '1' + result;
return result;
}
int main()
{
string str1 = "1100011";
string str2 = "10";
cout << "Sum is " << addBitStrings(str1, str2);
return 0;
}
|
Java
class GFG
{
static int makeEqualLength(StringBuilder str1,
StringBuilder str2)
{
int len1 = str1.length();
int len2 = str2.length();
if (len1 < len2)
{
for (int i = 0; i < len2 - len1; i++)
str1.insert(0, '0');
return len2;
}
else if (len1 > len2)
{
for (int i = 0; i < len1 - len2; i++)
str2.insert(0, '0');
}
return len1;
}
static String addBitStrings(StringBuilder str1,
StringBuilder str2)
{
String result = "";
int length = makeEqualLength(str1, str2);
String first = str1.toString();
String second = str2.toString();
int carry = 0;
for (int i = length - 1; i >= 0; i--)
{
int firstBit = first.charAt(i) - '0';
int secondBit = second.charAt(i) - '0';
int sum = (firstBit ^ secondBit ^ carry) + '0';
result = String.valueOf((char) sum) + result;
carry = (firstBit & secondBit) |
(secondBit & carry) |
(firstBit & carry);
}
if (carry == 1)
result = "1" + result;
return result;
}
public static void main(String[] args)
{
String str1 = "1100011";
String str2 = "10";
System.out.println("Sum is " +
addBitStrings(new StringBuilder(str1),
new StringBuilder(str2)));
}
}
|
Python3
def makeEqualLength(str1, str2):
len1 = len(str1)
len2 = len(str2)
if len1 < len2:
str1 = (len2 - len1) * '0' + str1
len1 = len2
elif len2 < len1:
str2 = (len1 - len2) * '0' + str2
len2 = len1
return len1, str1, str2
def addBitStrings( first, second ):
result = ''
length, first, second = makeEqualLength(first, second)
carry = 0
for i in range(length - 1, -1, -1):
firstBit = int(first[i])
secondBit = int(second[i])
sum = (firstBit ^ secondBit ^ carry) + 48
result = chr(sum) + result
carry = (firstBit & secondBit) | \
(secondBit & carry) | \
(firstBit & carry)
if carry == 1:
result = '1' + result
return result
if __name__ == '__main__':
str1 = '1100011'
str2 = '10'
print('Sum is', addBitStrings(str1, str2))
|
C#
using System;
using System.Text;
class GFG
{
static int makeEqualLength(StringBuilder str1,
StringBuilder str2)
{
int len1 = str1.Length;
int len2 = str2.Length;
if (len1 < len2)
{
for (int i = 0; i < len2 - len1; i++)
{
str1.Insert(0, '0');
}
return len2;
}
else if (len1 > len2)
{
for (int i = 0; i < len1 - len2; i++)
{
str2.Insert(0, '0');
}
}
return len1;
}
static string addBitStrings(StringBuilder str1,
StringBuilder str2)
{
string result = "";
int length = makeEqualLength(str1, str2);
string first = str1.ToString();
string second = str2.ToString();
int carry = 0;
for (int i = length - 1; i >= 0; i--)
{
int firstBit = first[i] - '0';
int secondBit = second[i] - '0';
int sum = (firstBit ^ secondBit ^ carry) + '0';
result = ((char) sum).ToString() + result;
carry = (firstBit & secondBit) |
(secondBit & carry) |
(firstBit & carry);
}
if (carry == 1)
{
result = "1" + result;
}
return result;
}
public static void Main(string[] args)
{
string str1 = "1100011";
string str2 = "10";
Console.WriteLine("Sum is " +
addBitStrings(new StringBuilder(str1),
new StringBuilder(str2)));
}
}
|
Javascript
function makeEqualLength(str1, str2)
{
var len1 = str1.length;
var len2 = str2.length;
if (len1 < len2)
{
for (var i = 0 ; i < len2 - len1 ; i++)
str1 = '0' + str1;
return len2;
}
else if (len1 > len2)
{
for (var i = 0 ; i < len1 - len2 ; i++)
str2 = '0' + str2;
}
return len1;
}
function addBitStrings(first, second )
{
var result = "";
var length = makeEqualLength(first, second);
var carry = 0;
for (var i = length-1 ; i >= 0 ; i--)
{
var firstBit = first[i] - '0';
var secondBit = second[i] - '0';
var sum = (firstBit ^ secondBit ^ carry) + 48;
result += String.fromCharCode(sum);
carry = (firstBit & secondBit) | (secondBit & carry) | (firstBit & carry);
}
if (carry)
result += '1';
return result;
}
var str1 = "1100011";
var str2 = "10";
console.log("Sum is " + addBitStrings(str1, str2));
|
Time Complexity: O(|str1|)
Auxiliary Space: O(1)
Method – 2 (without adding extra zeros(0) in beginning of a small length string to make both strings with same length)
Algo :
- make to pointer i,j and set i = str1.size() – 1 and j = str2.size() – 1
- take initial carry as 0 ans ans string as empty (“”)
- while i>=0 or j>=0 or carry
- add value of str1[i] and str2[j] in carry
- add (carry%2) in resulting(answer string) string
- set carry = carry/2
- return ans
C++
#include <bits/stdc++.h>
using namespace std;
string addBitStrings(string str1, string str2)
{
string ans = "";
int i = str1.size() - 1;
int j = str2.size() - 1;
int carry = 0;
while (i >= 0 || j >= 0 || carry) {
carry += ((i >= 0) ? (str1[i--] - '0') : (0));
carry += ((j >= 0) ? (str2[j--] - '0') : (0));
ans = char('0' + (carry % 2)) + ans;
carry = carry / 2;
}
return ans;
}
int main()
{
string str1 = "1100011";
string str2 = "10";
cout << "Sum is " << addBitStrings(str1, str2);
return 0;
}
|
Java
class GFG {
static String addBitStrings(StringBuilder str1,
StringBuilder str2)
{
StringBuilder ans = new StringBuilder();
int i = str1.length() - 1;
int j = str2.length() - 1;
int carry = 0;
while (i >= 0 || j >= 0 || carry>0) {
if (i >= 0)
carry += str1.charAt(i--) - '0';
if (j >= 0)
carry += str2.charAt(j--) - '0';
ans.append(carry % 2);
carry = carry/2;
}
return ans.reverse().toString();
}
public static void main(String[] args)
{
String str1 = "1100011";
String str2 = "10";
System.out.println("Sum is "+ addBitStrings(new StringBuilder(str1),
new StringBuilder(str2)));
}
}
|
Python3
def addBitStrings(str1, str2):
ans = ''
i = len(str1) - 1
j = len(str2) - 1
carry = 0
while i >= 0 or j >= 0 or carry:
if i >= 0:
carry += ord(str1[i]) - ord('0')
i = i - 1
else:
carry += 0
if j >= 0:
carry += ord(str2[j]) - ord('0')
j = j - 1
else:
carry += 0
ans = chr(ord('0') + carry % 2) + ans
carry = carry // 2
return ans
str1 = '1100011'
str2 = '10'
print('Sum is ', addBitStrings(str1, str2))
|
C#
using System;
public static class Globals
{
public static string addBitStrings(string str1,
string str2)
{
string ans = "";
int i = str1.Length - 1;
int j = str2.Length - 1;
int carry = 0;
while (i >= 0 || j >= 0 || carry != 0) {
carry += ((i >= 0) ? (str1[i--] - '0') : (0));
carry += ((j >= 0) ? (str2[j--] - '0') : (0));
ans = (char)('0' + (carry % 2)) + ans;
carry = carry / 2;
}
return ans;
}
public static void Main()
{
string str1 = "1100011";
string str2 = "10";
Console.Write("Sum is ");
Console.Write(addBitStrings(str1, str2));
}
}
|
Javascript
function addBitStrings(str1, str2)
{
let ans = "";
let i = str1.length - 1;
let j = str2.length - 1;
let carry = 0;
while (i >= 0 || j >= 0 || (carry != 0)) {
carry += ((i >= 0) ? (parseInt(str1[i--])) : (0));
carry += ((j >= 0) ? (parseInt(str2[j--])) : (0));
ans = (carry % 2).toString() + ans;
carry = Math.floor(carry / 2);
}
return ans;
}
let str1 = "1100011";
let str2 = "10";
console.log("Sum is", addBitStrings(str1, str2));
|
Time Complexity: O(max(n,m)) (where, n = sizeof str1 & m = sizeof str2)
Space Complexity: O(1)
This article is compiled by Ravi Chandra Enaganti. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
