### sar0603's blog

By sar0603, history, 3 years ago,
//S = bitmask representation of available subset
//{1,2,3} ,S = 3 means only {2,3} are available since binary(3) = 0 1 1

for (int G = S; G != 0 ; G = (G - 1) & S)


This one liner generates subset of a subset in bit representation form. Would be grateful if anyone can give any intuition or explain the above line. Dont want to mug this up.

Eg: ~~~~~ The subset = 1110 The subsets of subset : 1110 1100 1010 1000 0110 0100 0010 ~~~~~

• 0

| Write comment?
 » 3 years ago, # | ← Rev. 2 →   0 $G - 1$ remove rightmost set bit and make all other bit on the right side of it setted$10010101000... \rightarrow 10010100111...$$00010100000... \rightarrow 00010011111...$But not all of the left-part on right-side are included in $S$. So by doing $(G - 1)$ & $S$, you removed the rightmost bit and turn on all other bit included in $S$ in right side
•  » » 3 years ago, # ^ |   0 About the complexity. It is $O(3^n)$1) Since $S$ is a bitmask and $G$ is a submask. Hence $G \subseteq S \Rightarrow \forall\ x \in G \rightarrow x \in S$. For each bit $x$, there are 3 cases $x \in S$ and $x \in G$ $x \in S$ and $x \notin G$ $x \notin S$ and $x \notin G$ $\Rightarrow$ for $n$ bits, there are $O(3^n)$ cases2) Each submask is a combination with $k$ set bit in $n$ total bits and for each combination there are $2^k$ submasks. Hence, the number of submasks are$\overset{n}{\underset{k = 0}{\Sigma}} \binom{n}{k} \cdot 2^k = 3^n$