title: What is the logic behind binary comparison between elements and number of elements in finding a subset?
body: <p>Consider the following problem from a book (<a href="https://cses.fi/book/book.pdf" rel="nofollow noreferrer">https://cses.fi/book/book.pdf</a>): 
  "We first consider the problem of generating all subsets of a set of n elements. For example, the subsets of {0,1,2} are φ, {0}, {1}, {2}, {0,1}, {0,2}, {1,2} and {0,1,2}. There are two common methods to generate subsets: we can either perform a recursive search or exploit the bit representation of integers."</p>
  
  <p>Solution number 2 in the book (page 48, PDF page 58) is the following:</p>
  
  <pre class="lang-cpp prettyprint-override"><code>for (int b = 0; b &lt; (1&lt;&lt;n); b++) {
      vector&lt;int&gt; subset;
      for (int i = 0; i &lt; n; i++) {
          if (b&amp;(1&lt;&lt;i)) subset.push_back(i);
      }
  }
  </code></pre>
  
  <p>My question is: why does the <code>(b&amp;(1&lt;&lt;i))</code> comparison work? Just what is it doing in the background? I've tried it out by hand for the subsets of {0, 1}, and it works flawlessly, but just why do comparisons between them work? <code>b</code> is a counter for the number of elements and <code>(1&lt;&lt;i)</code>, from my understanding is basically equivalent to 2<sup>i</sup>. Why does it all work though? It seems like magic. </p>
  
  <p>PS. I know the book is a bad C++ reference, I'm reading it more so for algorithm explanations.</p>