Problem
Suppose, you’ve N elements and you need to find the subsets of these N elements where zero or more of the N elements are included or excluded in a subset.
All of these subsets are called the power set. The powerset of a set S is denoted as P(S) or 2S. If S is a set with the N number of elements, then the number of all the subsets (powerset) of S is 2n. This is also the reason of the notation 2S denoting the power set P(S).
Bitmasks
We know that integers are stored as a sequence of bits (0 & 1). Now suppose we need to represent a subset of N elements, we can use an integer 0 <= x < 2N such that, if ith bit of x is 1 it means ith element is included in the subset, and if ith bit of x is 0, the ith element is not included in the subset.
Let N = 3, then the powerset of N: 23 = 8 and 0 <= x < 8:
n2 n1 n0 0 0 0 (0) 0 0 1 (1) 0 1 0 (2) 0 1 1 (3) 1 0 0 (4) 1 0 1 (5) 1 1 0 (6) 1 1 1 (7) Here, x = 110(6) means a subset with element n0 excluded and elements n1 & n2 included in the subset.
Bitmask Operations
Multiplication & Division
Multiplication Let N = 28, N (binary representation) = (11100)2 (base 2) N << 1 (shifting bits left by 1) = 56 (111000)2 Shifting bits left by n, means multiplying by 2^n Division Similarly, shifting bits right by n, means dividing by 2^n, and we lose n least significant bits (ie. right-most bits) N = 27, (11011)2 N >> 1 (shifting bits right by 1) = 13 (1101)2 Here we divided by 2 and lost 1 least significant bit. If we shift by 2: N = N >> 2 N = 6 (110)2 (divided by 2^2 (4) and lost last 2 significant bits)
Including & Excluding the ith element
NOTE: Here elements are counted from the 0th bit
Including ith bit Let N = 28 (11100) and include the ith bit, i = 1 (2nd element): To include an element we will use OR (|) operator i = 1 << 1 = 00010 (2) N = N | i = 11110 (30) Excluding ith bit Let N = 28 (11100) and exclude the ith bit, i = 2 (3rd element) To exclude an element we will use AND (&) and NOT (~) operator i = ~(1 << 2) = ~(00100) = (11011) N = N & i = 11000 (24)
Check if the ith element is present
Let N = 28 (11100) and i = 2 (3rd element) To check if ith element is present, we will use AND (&) operator i = 1 << 2 x = N & i if x = 0, ith element is not present, if x = 1 ith element is present
Toggle the status of the ith element
Let N = 28 (11100) and i = 2 (3rd element) To toggle the status of if ith element, we will use XOR (^) operator i = 1 << 2 N = N^i = (11100)^(00100) = 11000 (24)
Practice Problem
Print all the subsets of the given set of N elements such that k elements (k1, k2, k3) are excluded in the subset. You’re given N and an array ki[] of k elements.
Constraints
- N <= 20
- k <= N
- ki < N
Sample Input
N = 3
k = 1
ki = {0}
Sample Output
000 010 100 110
Explanation
For N = 3, the subsets are as follows: n2 n1 n0 0 0 0 (0) 0 0 1 (1) 0 1 0 (2) 0 1 1 (3) 1 0 0 (4) 1 0 1 (5) 1 1 0 (6) 1 1 1 (7) Now, the subsets with n0 not included or n0 = 0 are the following: n2 n1 n0 0 0 0 (0) 0 1 0 (2) 1 0 0 (4) 1 1 0 (6)
Solution
Approach:
Since n is small, we can use a brute force approach of generating all the subsets (2n) and removing the ones that contain any of the excluded ki (k1, k2, k3..) element.
We’ll be using C++ STL Bitset for representing subsets. Bitset class is like Arrays but stores only boolean values (true/false, 0/1). Also, Bitset is optimized for space allocation: generally, each element occupies only one bit. You can read more about it here.
Code Implementation
//
// main.cpp
// Bitmask
//
// Created by Himanshu on 18/07/22.
//
#include<iostream>
#include<cmath>
#include <bitset>
#include<vector>
#define N 3
using namespace std;
void findSubsets (int k, int ki[]) {
long subsetCount = (long int)pow(2,(double)N);
for (long i=0; i<subsetCount; i++) {
int pos = 0; //variable for current bit position (0th - N-1th)
long x = i; //integer to be used for bitmasking (0 <= x < 2^N)
bool flag = false;
bitset<N> subset;
while (x > 0) {
//Checking if the last bit (rightmost bit (1 << 0)) is set or not
if (x&1) {
//Checking if the current bit is the excluded (ki) bit or not.
//Discarding this subset if it includes an excluded bit.
for (int j=0; j<k; j++) {
if (pos == ki[j]) {
flag = true;
}
}
if (flag) {
//Discarding this subset
break;
} else {
//Adding current bit to the subset
subset.set(pos, 1);
}
} else {
//Setting the current bit as 0 if it's unset in x
subset.set(pos, 0);
}
//shifting 1 bit to right, to check the next bit
//and incresing position (pos) of the current bit by 1
x = x >> 1;
pos++;
}
if (!flag) {
cout<<subset<<endl;
}
}
}
int main() {
int k = 1;
int *ki = new int[k]();
ki[0] = 0;
cout<<"Subsets with 0th bit unset:"<<endl;
findSubsets(k, ki);
return 0;
}
Output
Subsets with 0th bit unset: 000 010 100 110
Here’s a working example: Finding Subsets
Similar Practice Problems
One thought on “Bitmasking”