Сложите два числа без знака, используя биты

Опубликовано: 30 Декабря, 2021

Даны два целых числа без знака (максимально возможный ввод может состоять из 32 бита). Задача состоит в том, чтобы сложить два числа с помощью битовых операций.

Примеры:

 Ввод: n1 = 12, n2 = 34.
Выход: 46

Ввод: n1 = 12564 n2 = -1
Выход: 12563

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: поскольку мы знаем, что дополнительно

1 + 0 = 1
0 + 1 = 1
0 + 0 = 0
1 + 1 = 0 переносить 1
если (перенос == 1) 1 + 1 = 1 перенос 1

Представьте целое число с помощью функции набора битов в C ++. Он ведет себя как массив, который хранит LSB (наименьший значащий бит) в 0-м индексе, и когда мы печатаем такой массив, он печатает двоичное представление в обратном формате. Добавьте каждый бит справа в соответствии со свойством сложения битов и сохраните в третьем битовом наборе. Функция to_ulong () используется для преобразования битовой формы в десятичную.
Ниже представлена реализация описанного выше подхода.

C ++

 #include <bits/stdc++.h>
 #define M 32
 using namespace std;
 // Function to add two bitset
 int binAdd(bitset<M> atemp, bitset<M> btemp)
 {
    // To store the bits of answer
    bitset<M> ctemp;
    for ( int i = 0; i < M; i++)
        ctemp[i] = 0;
    // Initialize carry to 0
    int carry = 0; 
    for ( int i = 0; i < M; i++) { 
        // Both bits are zero
        if (atemp[i] + btemp[i] == 0) { 
            if (carry == 0)
                ctemp[i] = 0;
            else {
                ctemp[i] = 1;
                carry = 0;
            }
        }
        // Any of the one bit is 1
        else if (atemp[i] + btemp[i] == 1) { 
            if (carry == 0)
                ctemp[i] = 1;
            else {
                ctemp[i] = 0;
            }
        }
        // Both bits are 1
        else {
            if (carry == 0) {
                ctemp[i] = 0;
                carry = 1;
            }
            else {
                ctemp[i] = 1;
            }
        }
    }
    // To convert bitset into
    // decimal equivalent
    return ctemp.to_ulong();
 }
 // Driver Code
 int main()
 {
    int number1, number2;
    number1 = 12;
    number2 = 34;
    // Converting number 1 to bitset form
    bitset<M> num1(number1);
    // Converting number 2 to bitset form
    bitset<M> num2(number2);
    cout << binAdd(num1, num2) << endl;
 }

Джава

 // Java program to add two unsigned numbers using bits
 import java.util.*; // Needed for BitSet class.
 class GFG {
    static final int M = 32 ; 
    // Function to add two BitSets. Returns long number.
    static long binAdd(BitSet atemp, BitSet btemp)
    {
        // Initialize a 3rd BitSet to store the answer.
        BitSet ctemp = new BitSet(M);
        for ( int i = 0 ; i < M; i++) {
            ctemp.set(i, false );
        }
        // Initialize carry to ZERO.
        int carry = 0 ; 
        for ( int i = 0 ; i < M; i++) { 
            // Both of the bits are ZERO.
            if (atemp.get(i) == false
                && // Uses the "conditional-AND" operator
                   // (also known as "short-circuit AND")
                   // which is more efficient than the
                   // ordinary & bitwise operator.
                btemp.get(i) == false ) { 
                if (carry == 0 ) {
                    ctemp.set(i, false );
                }
                else {
                    ctemp.set(i, true );
                    carry = 0 ;
                }
            }
            // Either of the bits is a ONE but not both.
            else if (atemp.get(i) == true
                     ^ // Uses the "XOR" (exclusive-OR)
                       // operator to ensure that ONLY
                       // one of the two bits is a ONE.
                     btemp.get(i) == true ) { 
                if (carry == 0 ) {
                    ctemp.set(i, true );
                }
                else {
                    ctemp.set(i, false );
                }
            }
            // Both of the bits are ONE.
            else // By process of elimination we do not need
                 // to code for the (TRUE & TRUE) condition.
            {
                if (carry == 0 ) {
                    ctemp.set(i, false );
                    carry = 1 ;
                }
                else {
                    ctemp.set(i, true );
                }
            }
        }
        // Returns the 3rd BitSet as its decimal equivalent
        // number in long format.
        return ctemp.toLongArray()[ 0 ];
    }
    // Driver Code
    public static void main(String args[])
    {
        int number1, number2; 
        // binary literal for decimal 15.
        number1 = 15 ;
        // binary literal for decimal 85.
        number2 = 1 ;
        // result should be decimal 100.
        // Converting number1 to BitSet form.
        BitSet num1
            = BitSet.valueOf( new long [] { number1 }); 
        // Converting number2 to BitSet form.
        BitSet num2
            = BitSet.valueOf( new long [] { number2 }); 
        System.out.printf( "%d plus %d equals %d" , number1,
                          number2, binAdd(num1, num2));
        System.out.println();
    }
 }
 // This code is contributed by Arnab Kundu.
 // Modified by Matt Ambrose.

Python3

 # Python3 implementation of the approach
 # Function to convert given Integer
 # to list of bits of length M
 def bitset(num):
    
    return [ int (x) for x in format (num, '032b' )]
    
# Function to add two bitset
 def binAdd(atemp, btemp): 
    # To store the bits of answer
    ctemp = [ 0 ] * M
    
    # Initialize carry to 0
    carry = 0
    for i in range ( 0 , M): 
        # Both bits are zero
        if atemp[i] + btemp[i] = = 0 : 
            if carry = = 0 :
                ctemp[i] = 0 
            else :
                ctemp[i] = 1
                carry = 0
            
        # Any of the one bit is 1
        elif atemp[i] + btemp[i] = = 1 : 
            if carry = = 0 :
                ctemp[i] = 1
            else :
                ctemp[i] = 0 
        # Both bits are 1
        else :
            if carry = = 0 :
                ctemp[i] = 0
                carry = 1
            
            else :
                ctemp[i] = 1
            
    # To convert bitset into string and then
    # convert string to its decimal equivalent
    temp = ''.join([ str (x) for x in ctemp])
    return int (temp, 2 )
    
# Driver Code
 if __name__ = = "__main__" : 
    number1, number2 = 12 , 34
    M = 32
    
    # Converting number 1 to bitset form
    num1 = bitset(number1) 
    # Converting number 2 to bitset form
    num2 = bitset(number2) 
    print (binAdd(num1, num2))
    
# This code is contributed by Rituraj Jain

Выход

Хотите узнать о лучших видео и практических задачах, ознакомьтесь с базовым курсом C ++ для базового и продвинутого уровня C ++ и курсом C ++ STL для базового уровня плюс STL. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

C++

Сложите два числа без знака, используя биты

C ++

Джава

Python3

РЕКОМЕНДУЕМЫЕ СТАТЬИ