Find Subsets Using Bit Masking in C++ – A Complete Guide

Filed Under: C++
Find Subsets Using Bit Masking

In today’s article, we will learn to find subsets using bit masking. Bit masking is a very effective concept that can immensely help to optimize the code. We use bit masking to solve and optimize various problems like the N-Queens and today we’re here with another example making use of bitmasking. Without any further delay, let’s start learning.

What Are Sub-sequences?

A subsequence is a combination that can be formed by using any number of elements from a given sequence. While forming a subsequence from a sequence, we have two options for every element. Either we select this element as part of the subsequence, or we don’t, there’s no way around it.

As for every element we have 2 fundamental choices, which explains that the total number of subsequences for any sequence is 2N. Here N denotes the total number of elements in the subsequence.

One very basic difference between a substring and a subsequence is that substrings are continuous while subsequences are not.

Concept of Subsets and Bitmasking

In this article, we will limit our code to string-based sequences. Though the approach for all types of sequences is similar, we will only be working with strings.

Generating A Subsequence

For every character of the string, we have two options

  1. We select this element.
  2. Or we drop this element.

For the sake of understanding, let’s denote inclusion using 1 and exclusion using 0.

For example

Let's generate the subsets of "abc"
Total number of characters = 3
Hence, subsequences possible = 2^3 = 8
The 8 subsequences and their notations are:
" " = 000
"a" = 001
"b" = 010
"c" = 100
"ab" = 011
"ac" = 101
"bc" = 110
"abc" = 111

Our idea is to write a function filter that will take N and the string as the input, and generate all the possible subsequences. Then we will just iterate over the range 0 to (2N – 1). Every iteration will produce one subsequence of the given string. We will write the code in the following steps

  • Run a for loop from i = 0 to i = 2N – 1
  • Each value of i for this loop will denote a numerical equivalent of the subsequence
  • Now we will visualize this decimal number in binary form
  • Initialize an integer j with value 0. This variable will denote the position of a character
  • To do this, we will use a while loop
    • while(n > 0)
  • Inside this while loop we will extract each high bit of the variable i(numerical denoting a particular subsequence)
  • To extract the set bits from i number, we will use the following logic
    • while(i > 0)
      • int set_bit = (i & 1)
      • i == i >> 1
  • While doing this, for each iteration we will increment j. This while loop will run for log2i times.
  • And whenever we encounter a set bit we will print the element present at the position j.
filter(int N, char *s)
    for i <-- 0 to i <-- (1 << n - 1)
        j <-- 0
        while(n >0)
            last_bit <-- (n &1)
            if(last_bit)
                cout << s[j]
            j <-- j + 1
           n = n >> 1
           cout << endl
    return
Example 3
Example 3

Find Subsets Of A String Using Bit Masking in C++

Let’s now implement bitmasking in C++ by following the steps that we’ve discussed above.

#include <iostream>
#include <cstring>

using namespace std;

void filter(string s)
{
        for(int i = 0; i < 1 << s.length(); i++)
        {
                int j = 0;

                int n = i;

                cout << "[";
                while(n > 0)
                {
                        if(n & 1)
                                cout << s[j];
                        j++;
                        n = n >> 1;
                }
                cout << "]" << endl;
        }

        return;
}

int main()
{
        cout << "Enter a string" << endl;
        string s;
        cin >> s;

        filter(s);

        return 0;
}
Subsequence Function Code
Algorithm

Output

Program Output
Subsequence Using Bit Masking Output

Conclusion

In this article, we learned to find subsequence using bit masking. We use bit masking especially when we have a monotonous working region(states 0 to 2N in this case). Because using bit masking we can easily represent these values. That’s it for now, thanks for reading.

References

To learn more about recursion or bit masking, you can refer to the following websites.

https://www.journaldev.com/55710/tower-of-hanoi-in-c-solved

https://www.journaldev.com/57960/fast-exponentiation-using-bit-masking-using-c

close
Generic selectors
Exact matches only
Search in title
Search in content