A bitset is an array of boolean values, but each boolean value is not stored separately. Instead, bitset optimizes the space such that each bool takes 1-bit space only, so space taken by bitset say, bs is less than that of bool bs[N] and vector<bool> bs(N). However, a limitation of bitset is, N must be known at compile-time, i.e., a constant (this limitation is not there with vector and dynamic array)
Important Note:
- Take care of integer overflow say if bitset is declared of size 3 and addition results 9, this is the case of integer overflow because 9 cannot be stored in 3 bits.
- Take care for negative results as bitsets are converted to unsigned long integer, so negative numbers cannot be stored.
Addition of 2 bitsets: Follow the steps below to solve the problem:
- Initialize a bool carry to false.
- Create a bitset ans to store the sum of the two bitsets x and y.
- Traverse the length of the bitsets x and y and use the fullAdder function to determine the value of the current bit in ans.
- Return ans.
Below is the implementation of the above approach:
C++
// 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
Time Complexity: O(N), N is length of bitset
Auxiliary Space: O(N)
Subtraction of 2 bitsets: Follow the steps below to solve the problem:
- Initialize a bool borrow to false.
- Create a bitset ans to store the difference between the two bitsets x and y.
- Traverse the length of the bitsets x and y and use the fullSubtractor function to determine the value of the current bit in ans.
- Return ans.
Below is the implementation of the above approach:
C++
// 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
Time Complexity: O(N), N is length of bitset
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
