Bitmasking

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 2^S. If S is a set with the N number of elements, then the number of all the subsets (powerset) of S is 2ⁿ. This is also the reason of the notation 2^S 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 could 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: 2³ = 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 i^th 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 i^th 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 i^th 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
• k_i < 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 could use a brute force approach of generating all the subsets (2ⁿ) and removing the ones that contains 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 could 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 Problem
Codechef – Mike and Stamps