sar0603's blog

By sar0603, history, 4 years ago, In English
//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 ~~~~~

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

$$$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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)$$$ cases

    2) 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$$$