for (int b = 0; b < (1<<n); b++) {}
FULL MATTER->
Another way to generate subsets is based on the bit representation of integers.
Each subset of a set of n elements can be represented as a sequence of n bits,
which corresponds to an integer between 0β¦2
n β1. The ones in the bit sequence
indicate which elements are included in the subset.
The usual convention is that the last bit corresponds to element 0, the second
last bit corresponds to element 1, and so on. For example, the bit representation
of 25 is 11001, which corresponds to the subset {0,3,4}.
The following code goes through the subsets of a set of n elements
for (int b = 0; b < (1<<n); b++) {
// process subset
}
So, yeah <<
is the left shift operator in C/C++. Letβs say for x << k the output will be x*2^k because, what <<
does here is shifts the bits in the number x by k places to the left, so there will be k zeroes before these shifted bits, so x<<k = x*2^k. So, here in the code :
for(int b=0; b < (1<<n); b++) {
// something
}
since we know that there will be 2^n subsets for the set of size n .
we can run a loop in the interval [0,2^n), that is what this loop does, since (1<<n) == 2^n
1 Like
Thanks got it