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!
