Operaciones aritméticas con std::bitset en C++

Un conjunto de bits es una array de valores booleanos, pero cada valor booleano no se almacena por separado. En cambio, el conjunto de bits optimiza el espacio de modo que cada bool ocupa solo un espacio de 1 bit, por lo que el espacio ocupado por el conjunto de bits, por ejemplo, bs es menor que el de bool bs[N] y el vector <bool> bs(N) . Sin embargo, una limitación del conjunto de bits es que N debe conocerse en tiempo de compilación, es decir, una constante (esta limitación no existe con el vector y la array dinámica)

Nota IMPORTANTE:

• Tenga cuidado con el desbordamiento de enteros, por ejemplo, si el conjunto de bits se declara de tamaño 3 y la suma da como resultado 9, este es el caso de desbordamiento de enteros porque 9 no se puede almacenar en 3 bits.
• Tenga cuidado con los resultados negativos, ya que los conjuntos de bits se convierten en enteros largos sin signo, por lo que no se pueden almacenar números negativos.

Adición de 2 conjuntos de bits: siga los pasos a continuación para resolver el problema:

• Inicializar un acarreo bool a falso.
• Cree un conjunto de bits ans para almacenar la suma de los dos conjuntos de bits x e y.
• Recorra la longitud de los conjuntos de bits x e y y use la función fullAdder para determinar el valor del bit actual en ans .
• Regresar respuesta .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Utility function to add two bool values and calculate
// carry and sum
bool fullAdder(bool b1, bool b2, bool& carry)
{
    bool sum = (b1 ^ b2) ^ carry;
    carry = (b1 && b2) || (b1 && carry) || (b2 && carry);
    return sum;
}
// Function to add two bitsets
bitset<33> bitsetAdd(bitset<32>& x, bitset<32>& y)
{
    bool carry = false;
    // bitset to store the sum of the two bitsets
    bitset<33> ans;
    for (int i = 0; i < 33; i++) {
        ans[i] = fullAdder(x[i], y[i], carry);
    }
    return ans;
}
// Driver Code
int main()
{
    // Given Input
    bitset<32> a(25);
    bitset<32> b(15);
  
    // Store the result of addition
    bitset<33> result = bitsetAdd(a, b);
  
    cout << result;
    return 0;
}

000000000000000000000000000101000

Complejidad de tiempo: O(N), N es la longitud del conjunto de bits
Espacio auxiliar: O(N)

Resta de 2 conjuntos de bits: siga los pasos a continuación para resolver el problema:

• Inicialice un préstamo bool a falso.
• Cree un conjunto de bits para almacenar la diferencia entre los dos conjuntos de bits x e y.
• Recorra la longitud de los conjuntos de bits x e y y use la función fullSubtractor para determinar el valor del bit actual en ans .
• Regresar respuesta .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Utility function to subtract two bools and calculate diff
// and borrow
bool fullSubtractor(bool b1, bool b2, bool& borrow)
{
    bool diff;
    if (borrow) {
        diff = !(b1 ^ b2);
        borrow = !b1 || (b1 && b2);
    }
    else {
        diff = b1 ^ b2;
        borrow = !b1 && b2;
    }
    return diff;
}
// Function to calculate difference between two bitsets
bitset<33> bitsetSubtract(bitset<32> x, bitset<32> y)
{
    bool borrow = false;
    // bitset to store the sum of the two bitsets
    bitset<33> ans;
    for (int i = 0; i < 32; i++) {
        ans[i] = fullSubtractor(x[i], y[i], borrow);
    }
    return ans;
}
// Driver Code
int main()
{
    // Given Input
    bitset<32> a(25);
    bitset<32> b(15);
  
    // Store the result of addition
    bitset<33> result = bitsetSubtract(a, b);
  
    cout << result;
    return 0;
}

000000000000000000000000000001010

Complejidad de tiempo: O(N), N es la longitud del conjunto de bits
Espacio auxiliar: O(N)