Рубрики

Добавьте две битовые строки

Используя две битовые последовательности в виде строк, напишите функцию, которая возвращает сложение двух последовательностей. Битовые строки также могут быть разной длины. Например, если строка 1 имеет значение «1100011», а вторая строка 2 — «10», функция должна вернуть «1100101».

Мы настоятельно рекомендуем вам нажать здесь и попрактиковаться, прежде чем переходить к решению.

Поскольку размеры двух строк могут быть разными, мы сначала делаем размер меньшей строки равным размеру большей строки, добавляя начальные 0. Сделав одинаковые размеры, мы по одному добавляем биты от крайнего правого к левому. В каждой итерации нам нужно суммировать 3 бита: 2 бита из 2 заданных строк и перенос. Бит суммы будет равен 1, если либо установлены все 3 бита, либо установлен один из них. Таким образом, мы можем сделать XOR всех битов, чтобы найти бит суммы. Как найти перенос — перенос будет равен 1, если установлен любой из двух битов. Таким образом, мы можем найти перенос, взяв ИЛИ всех пар. Ниже приведен пошаговый алгоритм.

1. Сделайте их равными по размеру, добавив 0 в начале меньшей строки.
2. Выполнить сложение бит
… ..Boolean выражение для добавления 3 битов a, b, c
… ..Сумма = a XOR b XOR c
… ..Carry = (a И b) ИЛИ (b И c) ИЛИ (c И a)

Ниже приведена реализация вышеуказанного алгоритма.

C ++

#include <iostream>

using namespace std;

  
// добавляем двухбитовые строки и возвращаем результат
string addBitStrings( string first, string second );

  
// Вспомогательный метод: учитывая две битовые строки неравного размера, преобразует их в
// той же длины, добавляя начальные 0 в меньшую строку. Возвращает
// новая длина

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; // Если len1> = len2

}

  
// Основная функция, которая добавляет двухбитовые последовательности и возвращает сложение
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';

  

        // логическое выражение для суммы 3 бит

        int sum = (firstBit ^ secondBit ^ carry)+'0';

  

        result = (char)sum + result;

  

        // логическое выражение для 3-битного сложения

        carry = (firstBit & secondBit) | (secondBit & carry) | (firstBit & carry);

    }

  

    // если переполнить, то добавить ведущий 1

    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

{

  

    // Вспомогательный метод: учитывая две битовые строки неравного размера,

    // конвертируем их в одинаковую длину, добавляя начальные 0

    // в меньшей строке. Возвращает новую длину

    // Использование StringBuilder в качестве Java использует только вызов по значению

    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; // Если len1> = len2

    }

  

    // Основная функция, которая добавляет двухбитовые последовательности

    // и возвращает сложение

    static String addBitStrings(StringBuilder str1,

                                StringBuilder str2) 

    {

        String result = ""; // Для хранения битов суммы

  

        // сделать одинаковые длины перед добавлением

        int length = makeEqualLength(str1, str2);

  

        // Преобразование StringBuilder в строки

        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';

  

            // логическое выражение для суммы 3 бит

            int sum = (firstBit ^ secondBit ^ carry) + '0';

  

            result = String.valueOf((char) sum) + result;

  

            // логическое выражение для 3-битного сложения

            carry = (firstBit & secondBit) | 

                    (secondBit & carry) | 

                    (firstBit & carry);

        }

          

        // если переполнить, то добавить ведущий 1

        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

# Python3 программа для вышеуказанного подхода

  
# добавляет двухбитные строки и возвращает результат

  
# Вспомогательный метод: с учетом двух битовых строк неравного размера,
# конвертирует их в одинаковую длину, добавляя начальные 0
# в меньшей строке. Возвращает новую длину

def makeEqualLength(str1, str2):

  

    len1 = len(str1)     # Длина строки 1

    len2 = len(str2)     # длина строки 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 = '' # Для хранения битов суммы

  

    # сделать длины одинаковыми перед добавлением

    length, first, second = makeEqualLength(first, second)

  

    carry = 0 # инициализировать перенос как 0

  

    # Добавить все биты один за другим

    for i in range(length - 1, -1, -1):

        firstBit = int(first[i])

        secondBit = int(second[i])

  

        # логическое выражение для суммы 3 бит

        sum = (firstBit ^ secondBit ^ carry) + 48

        result = chr(sum) + result

  

        # логическое выражение для сложения 3 бит

        carry = (firstBit & secondBit) | \

                (secondBit & carry) | \

                (firstBit & carry)

  

        # если переполнить, то добавить ведущий 1

    if carry == 1:

        result = '1' + result

    return result

  
Код водителя

if __name__ == '__main__':

    str1 = '1100011'

    str2 = '10'

    print('Sum is', addBitStrings(str1, str2))

      
# Этот код предоставлен
# chaudhary_19 (Mayank Chaudhary)

C #

// C # реализация вышеуказанного алгоритма

using System;

using System.Text;

  

class GFG

{

  

    // Вспомогательный метод: даны два неравных размера

    // битовые строки, преобразует их в одинаковую длину

    // добавляя начальные 0 в меньшую строку.

    // Возвращает новую длину, используя StringBuilder

    // поскольку Java использует только вызов по значению

    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; // Если len1> = len2

    }

  

    // Основная функция, которая добавляет двухбитовые последовательности

    // и возвращает сложение

    static string addBitStrings(StringBuilder str1, 

                                StringBuilder str2)

    {

        string result = ""; // Для хранения битов суммы

  

        // сделать одинаковые длины перед добавлением

        int length = makeEqualLength(str1, str2);

  

        // Преобразование StringBuilder в строки

        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';

  

            // логическое выражение для суммы 3 бит

            int sum = (firstBit ^ secondBit ^ carry) + '0';

  

            result = ((char) sum).ToString() + result;

  

            // логическое выражение для 3-битного сложения

            carry = (firstBit & secondBit) | 

                       (secondBit & carry) | 

                        (firstBit & carry);

        }

  

        // если переполнить, то добавить ведущий 1

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

    }

}

  
// Этот код предоставлен kumar65

Выход:

 Sum is 1100101

Эта статья составлена Рави Чандрой Энаганти . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Добавьте две битовые строки

0.00 (0%) 0 votes