Dadas dos secuencias de bits como strings, escriba una función para devolver la suma de las dos secuencias. Las strings de bits también pueden tener diferentes longitudes. Por ejemplo, si la string 1 es «1100011» y la segunda string 2 es «10», la función debería devolver «1100101».
Le recomendamos encarecidamente que haga clic aquí y lo practique antes de pasar a la solución.
Dado que los tamaños de dos strings pueden ser diferentes, primero hacemos que el tamaño de una string más pequeña sea igual al de la string más grande agregando ceros iniciales. Después de hacer que los tamaños sean iguales, agregamos bits uno por uno desde el bit más a la derecha hasta el bit más a la izquierda. En cada iteración, necesitamos sumar 3 bits: 2 bits de 2 strings dadas y llevar. El bit de suma será 1 si se establecen los 3 bits o se establece uno de ellos. Entonces podemos hacer XOR de todos los bits para encontrar el bit de suma. Cómo encontrar el acarreo: el acarreo será 1 si se establece cualquiera de los dos bits. Entonces podemos encontrar el acarreo tomando OR de todos los pares. El siguiente es el algoritmo paso a paso.
1. Hágalos del mismo tamaño agregando 0 al comienzo de la string más pequeña.
2. Realice la suma de bits
…..Expresión booleana para sumar 3 bits a, b, c
…..Sum = a XOR b XOR c
…..Carry = (a Y b) O (b Y c) O (c Y a)
A continuación se muestra la implementación del algoritmo anterior.
C++
#include <iostream>
using namespace std;
//adds the two-bit strings and return the result
string addBitStrings( string first, string second );
// Helper method: given two unequal sized bit strings, converts them to
// same length by adding leading 0s in the smaller string. Returns the
// new length
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; // If len1 >= len2
}
// The main function that adds two-bit sequences and returns the addition
string addBitStrings( string first, string second )
{
string result; // To store the sum bits
// make the lengths same before adding
int length = makeEqualLength(first, second);
int carry = 0; // Initialize carry
// Add all bits one by one
for (int i = length-1 ; i >= 0 ; i--)
{
int firstBit = first.at(i) - '0';
int secondBit = second.at(i) - '0';
// boolean expression for sum of 3 bits
int sum = (firstBit ^ secondBit ^ carry)+'0';
result = (char)sum + result;
// boolean expression for 3-bit addition
carry = (firstBit & secondBit) | (secondBit & carry) | (firstBit & carry);
}
// if overflow, then add a leading 1
if (carry)
result = '1' + result;
return result;
}
// Driver program to test above functions
int main()
{
string str1 = "1100011";
string str2 = "10";
cout << "Sum is " << addBitStrings(str1, str2);
return 0;
}
Java
// Java implementation of above algorithm
class GFG
{
// Helper method: given two unequal sized bit strings,
// converts them to same length by adding leading 0s
// in the smaller string. Returns the new length
// Using StringBuilder as Java only uses call by value
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; // If len1 >= len2
}
// The main function that adds two-bit sequences
// and returns the addition
static String addBitStrings(StringBuilder str1,
StringBuilder str2)
{
String result = ""; // To store the sum bits
// make the lengths same before adding
int length = makeEqualLength(str1, str2);
// Convert StringBuilder to Strings
String first = str1.toString();
String second = str2.toString();
int carry = 0; // Initialize carry
// Add all bits one by one
for (int i = length - 1; i >= 0; i--)
{
int firstBit = first.charAt(i) - '0';
int secondBit = second.charAt(i) - '0';
// boolean expression for sum of 3 bits
int sum = (firstBit ^ secondBit ^ carry) + '0';
result = String.valueOf((char) sum) + result;
// boolean expression for 3-bit addition
carry = (firstBit & secondBit) |
(secondBit & carry) |
(firstBit & carry);
}
// if overflow, then add a leading 1
if (carry == 1)
result = "1" + result;
return result;
}
// Driver Code
public static void main(String[] args)
{
String str1 = "1100011";
String str2 = "10";
System.out.println("Sum is " +
addBitStrings(new StringBuilder(str1),
new StringBuilder(str2)));
}
}
// This code is contributed by Vivek Kumar Singh
Python3
# Python3 program for above approach
# adds the two-bit strings and return the result
# Helper method: given two unequal sized bit strings,
# converts them to same length by adding leading 0s
# in the smaller string. Returns the new length
def makeEqualLength(str1, str2):
len1 = len(str1) # Length of string 1
len2 = len(str2) # length of string 2
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 = '' # To store the sum bits
# make the lengths same before adding
length, first, second = makeEqualLength(first, second)
carry = 0 # initialize carry as 0
# Add all bits one by one
for i in range(length - 1, -1, -1):
firstBit = int(first[i])
secondBit = int(second[i])
# boolean expression for sum of 3 bits
sum = (firstBit ^ secondBit ^ carry) + 48
result = chr(sum) + result
# boolean expression for 3 bits addition
carry = (firstBit & secondBit) | \
(secondBit & carry) | \
(firstBit & carry)
# if overflow, then add a leading 1
if carry == 1:
result = '1' + result
return result
# Driver Code
if __name__ == '__main__':
str1 = '1100011'
str2 = '10'
print('Sum is', addBitStrings(str1, str2))
# This code is contributed by
# chaudhary_19 (Mayank Chaudhary)
C#
// C# implementation of above algorithm
using System;
using System.Text;
class GFG
{
// Helper method: given two unequal sized
// bit strings, converts them to same length
// by adding leading 0s in the smaller string.
// Returns the new length Using StringBuilder
// as Java only uses call by value
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; // If len1 >= len2
}
// The main function that adds two-bit sequences
// and returns the addition
static string addBitStrings(StringBuilder str1,
StringBuilder str2)
{
string result = ""; // To store the sum bits
// make the lengths same before adding
int length = makeEqualLength(str1, str2);
// Convert StringBuilder to Strings
string first = str1.ToString();
string second = str2.ToString();
int carry = 0; // Initialize carry
// Add all bits one by one
for (int i = length - 1; i >= 0; i--)
{
int firstBit = first[i] - '0';
int secondBit = second[i] - '0';
// boolean expression for sum of 3 bits
int sum = (firstBit ^ secondBit ^ carry) + '0';
result = ((char) sum).ToString() + result;
// boolean expression for 3-bit addition
carry = (firstBit & secondBit) |
(secondBit & carry) |
(firstBit & carry);
}
// if overflow, then add a leading 1
if (carry == 1)
{
result = "1" + result;
}
return result;
}
// Driver Code
public static void Main(string[] args)
{
string str1 = "1100011";
string str2 = "10";
Console.WriteLine("Sum is " +
addBitStrings(new StringBuilder(str1),
new StringBuilder(str2)));
}
}
// This code is contributed by kumar65
Javascript
// JavaScript code to implement the approach
// Helper method: given two unequal sized bit strings, converts them to
// same length by adding leading 0s in the smaller string. Returns the
// new length
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; // If len1 >= len2
}
// The main function that adds two-bit sequences and returns the addition
function addBitStrings(first, second )
{
var result = ""; // To store the sum bits
// make the lengths same before adding
var length = makeEqualLength(first, second);
var carry = 0; // Initialize carry
// Add all bits one by one
for (var i = length-1 ; i >= 0 ; i--)
{
var firstBit = first[i] - '0';
var secondBit = second[i] - '0';
// boolean expression for sum of 3 bits
var sum = (firstBit ^ secondBit ^ carry) + 48;
result += String.fromCharCode(sum);
// boolean expression for 3-bit addition
carry = (firstBit & secondBit) | (secondBit & carry) | (firstBit & carry);
}
// if overflow, then add a leading 1
if (carry)
result += '1';
return result;
}
// Driver program to test above functions
var str1 = "1100011";
var str2 = "10";
console.log("Sum is " + addBitStrings(str1, str2));
// This code is contributed by phasing17
Producción
Sum is 1100101
Complejidad de tiempo: O(|str1|)
Espacio Auxiliar: O(1)
Método: 2 (sin agregar ceros adicionales (0) al comienzo de una string de longitud pequeña para hacer que ambas strings tengan la misma longitud)
algo:
- haga el puntero i,j y establezca i = str1.size() – 1 y j = str2.size() – 1
- tomar el acarreo inicial como 0 y la string como vacía («»)
- mientras que i>=0 o j>=0 o llevar
- agregar valor de str1[i] y str2[j] en carry
- agregar (llevar% 2) en la string resultante (string de respuesta)
- establecer acarreo = acarreo/2
- volver y
C++
#include <bits/stdc++.h>
using namespace std;
// The function that adds two-bit sequences and returns the addition
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;
}
// Driver program to test above functions
int main()
{
string str1 = "1100011";
string str2 = "10";
cout << "Sum is " << addBitStrings(str1, str2);
return 0;
}
Java
// Java implementation
class GFG {
// The main function that adds two-bit
// sequences and returns the addition
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();
}
// Driver Code
public static void main(String[] args)
{
String str1 = "1100011";
String str2 = "10";
System.out.println("Sum is "+ addBitStrings(new StringBuilder(str1),
new StringBuilder(str2)));
}
}
// This code is contributed by ajaymakvana
Python3
# The function that adds two-bit sequences and returns the addition
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
# Driver program to test above functions
str1 = '1100011'
str2 = '10'
print('Sum is ', addBitStrings(str1, str2))
# This code is contributed by ajaymakavan.
C#
// C# code to implement the approach
using System;
public static class Globals
{
// The function that adds two-bit sequences and returns
// the addition
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;
}
// Driver program to test above functions
public static void Main()
{
string str1 = "1100011";
string str2 = "10";
Console.Write("Sum is ");
Console.Write(addBitStrings(str1, str2));
}
}
// This code is contributed by Aarti_Rathi
Javascript
// JavaScript code to implement the approach
// The function that adds two-bit sequences and returns the addition
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;
}
// Driver program to test above functions
let str1 = "1100011";
let str2 = "10";
// Function Call
console.log("Sum is", addBitStrings(str1, str2));
// This code is contributed by phasing17
Producción
Sum is 1100101
Time Complexity: O(max(n,m)) (where, n = sizeof str1 & m = sizeof str2) Space Complexity: O(1)
Este artículo ha sido compilado por Ravi Chandra Enaganti . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA