The magic of bitmasks

Consider the simple problem of iterating over all the subsets of a given set. For years I’ve been using recursion to do this, until I came across this neat trick. The magic is contained in the fact that every integer has a binary form, and we can use the individual bits to represent elements in a set. Confused? Have a look at these numbers :

0, 1, 2, 3, 4, 5, 6, 7

Still doesn’t make sense? Let’s write them out in binary :

000, 001, 010, 011, 100, 101, 110, 111

See something now? Aha! If we use the position of the 1s to correspond to a particular element in a 3-element subset, we have just generated all of it’s subsets by just running through a list of increasing numbers! Well, not quite. There is still the simple matter of using the information in these binary numbers to do the actual listing.

We can check if a particular bit is set by using the bitwise-AND operator. By looking at which bits are set and displaying the element only if it’s corresponding bit is set, we can write a simple subset listing program :

#include <iostream>
using namespace std;

int main()
{
   char arr[] = "abc";

   for(int i=0 ; i<8 ; i++)
   {
      for(int j=0 ; j<3 ; j++)
         if(i & (1<<j))
            cout << arr[j];
      cout << endl;
   }

   return 0;
}

This is a small example that works on a set of 3 elements. How about larger sets? No problem! However, you are bounded by the size of the integer that you use. So if you use a 32-bit integer, you cannot use this trick on sets with more than 31 elements.

Also, keep in mind that a set with N elements has 2^N subsets (including the null subset).

Let’s put this idea into a program that works on strings of variable length :

#include <iostream>
#include <cstring>
using namespace std;

int main()
{
   char arr[50];

   cout << "Enter string : ";
   cin >> arr;

   int len = strlen(arr);

   if(len >= 8 * sizeof(int))
   {
      cout << "String too long!\n";
      return 1;
   }

   for(int i=0 ; i < (1<<len) ; i++)
   {
      for(int j=0 ; j < len ; j++)
         if(i & (1<<j))
            cout << arr[j];
      cout << endl;
   }

   return 0;
}

Advertisement