**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^{n}. 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 < 2`

such that, if ^{N}`i`

it means ^{th} bit of x is 1`i`

element is included in the subset, and if ^{th}`i`

, the ^{th} bit of x is 0`i`

element is not included in the subset.^{th}

Let N = 3, then the powerset of N: 2^{3} = 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

MultiplicationLet 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^nDivisionSimilarly, 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 bitLet N = 28 (11100) and include the i^{th}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 bitLet N = 28 (11100) and exclude the i^{th}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 i^{th}element is present, we will use AND (&) operator i = 1 << 2 x = N & i if x = 0, i^{th}element is not present, if x = 1 i^{th}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 i^{th}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 k_{i}= {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^{n}) 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

## One thought on “Bitmasking”