Hello all,
The programming club of my college is new and students are not familiar with many algorithms yet (including me :)). So they ask me a lot of problems. Among those, most of my friends and juniors have asked me about bitmasking and they can’t find many resource on the internet (well, I learnt it online, from codechef). So I have decided to write a small tutorial.
N.B. Please point out if anything is wrong or should be presented in a different way. All criticisms are welcome 
Let’s begin :
Bit masking is used to find all the subsets of an array. In this method, we create a one-to-one mapping between all subsets and the natural numbers.
Consider the first eight numbers and their binary representation.
0 - 000
1 - 001
2 - 010
3 - 011
4 - 100
5 - 101
6 - 110
7 - 111
Let’s say the contents of the array is {a,b,c}
a is at position 1
b is at position 2
c is at position 3
Consider a subset ac. In this subset, the element at first position of the array is taken. The element at second position is ignored. Again the element at third position is taken.
Let’s write it as : 101
where 1 at a position indicates the element in the array at that position is taken in the subset. 0 means it is ignored.
So, 110 will indicate :
element at first and second positions are taken, third one is ignored. So the subset it represents is ab.
The array {a,b,c} has three elements. So the number of subsets is 2^3 = 8
Let’s write all the subsets in the above mentioned binary notation and let’s write the binary numbers in their decimal representation
000 - empty set - 0
001 - c - 1
010 - b - 2
011 - bc - 3
100 - a - 4
101 - ac - 5
110 - ab - 6
111 - abc - 7
See all the subsets are covered and each subset is identified by a natural number (including 0) from the set [0,2^n-1], where n is the size of the array.
Now let’s come to implementation part :
We can iterate through all numbers from 0 to 2^n-1 and check which bits are set in the number in its binary form. If a bit is set, we include the element of the array at that position in our present subset.
Now, how to check which bit is set? Consider the number 5 (101 in binary).
101 & 001 = 1 (ANDing with 2^0)
101 & 010 = 0 (ANDing with 2^1)
101 & 100 = 1 (ANDing with 2^2)
So,if ANDing with 2^x gives 1, then (x+1)th bit from right (counting starting at 1) is set.
C/C++, java gives shift operator (<<) (I don’t know about other programming languages). 1<<x means 1 is shifted to the left x times. So,
1<<0 = 001 = 2^0
1<<1 = 010 = 2^1
1<<2 = 100 = 2^2, ans so on
So, by ANDing the number with 1<<x, where x can be from 0 to n-1, we can check which bit is set.
Here’s the pseudo code to print all the subsets or array (say arr[]) of size (say n).
for(mask=0 ; mask < pow(2,n) - 1 ;mask++)
{
for(i=0;i < n;i++)
{
if(mask & (1<<i))
{
printf("%d",arr[n-i-1]);
}
}
}
I hope everything above is understandable.
N.B. The complexity of the method is O(2^n * n), as for loop iterates through [0,2^n-1] and second loop runs for n times. So this method is extremely slow. For n=20, it takes about a second. Let’s say it takes exactly 1 second. Then for n=21, the number of subsets is 2^21, which is 2 times more than when n=20. So for n=21, it will roughly take 2 seconds. Similarly for each increase in the number of elements in the array, the time taken by the code roughly doubles. It will take more than 10 days for n=40. So use it when n<=20.
Problems to practice :