Bit-masking in DP

Bit-masking

generally uses the concept of representing number in form of bits and then performing the required operations .
(usually used for the selection process in a given set , a given element)
lets take an example

Let there be an set of 4 elements {3,5,2,1}
Now we want to all the different elements we can make by selecting some the elements out of this set ,
so what are the possible sums.
To find that out we will have to take out numbers out of sets in different combinations

how to think of selection out of sets in terms of maths and computer programming
Here comes the role of Bit masking P)

out of the set we either select the number or dont select it , that makes it a _ _ _ _ (four dashes of true or false)
we plan to represent these four dashes as 0 or 1 .(which makes it binary)
so the possible representations can be
0 0 1 0 ---> if we select only 2 that is 3rd element and sum becomes 2
0 1 0 1 ---> if we select both 5 and 1 , that sums up to 6

This binary representation is good , but now we need to help ourselves to use it more efficiently
alas we plan to convert into decimal and work upon it, and use that as binary as per when required

we will be able to use this concept whenever the number of elements in the set happens to be less equal to 64( for we can represent max of 64 bit in a computer)

any time with n elements in the set and max possible combination will be 2^n
In the above case its 2^4 that is 16
from
0 0 0 0 - - - when we select no element TO
1 1 1 1 - - - when we select all (decimal 15)

pseudo algo

int n // number of elements in a set

int tp=1<<n   // 2^n  total possible combination

for(int i=0;i<tp;i++)
{
for(int j=0;j<n;j++)// here we will work on whether we will select the element or not as per i
{
if((1<<j)&i) // if the particular bit of i is on , then true ,(*) explined at bottom
{
//select it
}
}

}

if i is 5 0101
loop over j (0 to 3)
0 -> 2^0     0 0 0 1 & 0 1 01 so true
1-> 2^1      0 0 1 0 & 0 1 0 1 so false
2->2^2       0 1 0 0 & 0 1 0 1 so true
3->2^3       1 0 0 0 & 0 1 0 1 so false

hence 5 and 1 are selected

question

http://community.topcoder.com/stat?c=problem_statement&pm=13166

solution

http://community.topcoder.com/stat?c=problem_solution&cr=22777422&rd=15854&pm=13166