First thing to make sure before using bitmasks for solving a problem is that it must be having small constraints, as solutions which use bitmasking generally take up exponential time and memory.
Let’s first try to understand what Bitmask means. Mask in Bitmask means hiding something. Bitmask is nothing but a binary number that represents something. Let’s take an example. Consider the set A={1,2,3,4,5}. We can represent any subset of A using a bitmask of length 5, with an assumption that if ith(0≤i≤4) bit is set then it means ith element is present in subset. So the bitmask 01010 represents the subset {2,4}
Now the benefit of using bitmask. We can set the ith bit, unset the ith bit, check if ith bit is set in just one step each. Let’s say the bitmask, b=01010.
* Set the ith bit: b|(1<<i). Let i=0, so,(1<<i)=0000101010|00001=01011So now the subset includes the 0th element also, so the subset is {1,2,4}.
* Unset the ith bit: b&!(1<<i). Let i=1, so,(1<<i)=00010!(1<<i)=1110101010&11101=01000Now the subset does not include the 1st element, so the subset is {4}.
* Check if ith bit is set: b&(1<<i), doing this operation, if ith bit is set, we get a non zero integer otherwise, we get zero. Let i=3(1<<i)=0100001010&01000=01000Clearly the result is non-zero, so that means 3rd element is present in the subset.