The Art of BitMasking

Shakib Ahmed
Bits and Pieces
Published in
4 min readApr 22, 2019
Bitmasking is a very powerful technique used in Programming

Hello World! You must have come across a question in Programming where you have to generate all the subsets of a given set and perform some operations on those subsets and what we usually do is use recursion to generate all the subsets BUT there is also another way to perform that task iteratively and that too without using any extra function meaning no function call overhead.

We are talking of BitMasking here. We first keep in mind that an integer is just a bunch of bits stringed together. In Bitmasking, the idea is to visualize a number in the form of its binary representation. Some bits are “set” and some are “unset” , “set” means its value is 1 and “unset” means its value is 0.

A “Bitmask” is simply a binary number that represents something.

Suppose ‘n’ is the number of elements in our set. Then, If we write the binary representation of all numbers from 0 to (2^n)-1, we get all the possible combinations of selecting n items. Let's take an example:

suppose the set we have is {1 2 3} and we want to get all the possible combinations of selecting the given 3 items of the set. Then (2^3)-1 is 7 , so we write all the numbers from 0 to 7 and binary representation of those numbers will give us the possible combinations of selecting the 3 items.                                          {1 2 3}
Number Binary Representation Subset
0 0 0 0 { }
1 0 0 1 { 3}
2 0 1 0 { 2 }
3 0 1 1 { 2 3}
4 1 0 0 {1 }
5 1 0 1 {1 3}
6 1 1 0 {1 2 }

7 1 1 1 {1 2 3}

In this way, we have actually generated all of our subsets😎

‘Mask’ means hiding something, The binary representations of 1,2,3,….,7 actually represent a mask. In a particular subset, the i-th element of the set belongs to it if and only if the i-th bit of the mask is set (value is 1).
As shown in the above example: If a bit is set (value is 1), then we take the corresponding element from our array in our subset. For example, in the binary representation of 1, i.e. 001 the 3rd bit is set, so we take the 3rd element in our subset and ignore the 1st and 2nd element. For 6, the binary representation is 110 so we take the 1st and 2nd element in our subset and ignore the 3rd element.

‘Mask’ means hiding something (via giphy)

Note: Actually, the first bit will always be the least significant bit and will always appear at the very right, that means in 001, the 1st bit is set so it actually represents {1}, in 110 the 2nd and 3rd bit are set, representing {2, 3}. We have taken the representation in the above example simply for better understanding because when we implement it, that order doesn’t actually matter so we can safely visualize it in the way shown in the above example.

We can perform the following useful operations on Bitmasks:
Let ‘B’ represent a bitmask
1) Set the i-th bit : B = B | (1<<i)
2) Unset the i-th bit:
B = B &! (1<<i)
3) Check if i-th bit is set:
B & (1<<i) if i-th bit is set, we get a non-zero integer otherwise we get a zero
4) Toggle the i-th item of the set: B =B ^ (1<<i)
5) Turn On all the bits in a set of size ‘n’: B = (1<<n)-1

Now, one more important thing to note is that the total number of possible subsets is 2^n, so to iterate through all the subsets of a set of size ’n’, we have to run the loop 2^n times and 2^n = (1<<n), so we simply run the loop (1<<n) times.

Implementation:
Enough theory, let's see the implementation part

Algorithm:
1. Run a loop for ‘mask’ for all numbers from 0 to (2^n)-1.
2. When inside this loop, run a loop for ‘i’ from 0 to n-1.
3. Inside this loop, check if the i-th bit is set(value is 1).
4. If i-th bit is set, then we include this element in our subset, otherwise not.
5. Done.

visit GitHub

Implementation Note:

But remember what Uncle Ben said to Peter (via giphy)

So, we have seen that Bitmasking is a very useful technique but we have to use it carefully:
1) The solutions which use bitmasking generally take exponential time.
The time complexity of the above code is O((2^n) * n), so use it for small constraints only(generally for n≤20).
2) Check the size of the set to decide whether to use ‘int’ or ‘long long int’, if the size of the set is greater than 20, then it is advisable to not to use Bitmasking at all
3) Use parenthesis when dealing with Bitwise operators.

So that’s all for today. Any suggestions? Let me know in the comments!
Till then Tschüß!

Published in Bits and Pieces

Insightful articles, step-by-step tutorials, and the latest news on full-stack composable software development

Responses (1)

What are your thoughts?