title: What is the best way to loop through integers with at most k bits ON?
body: <p>I need to loop through all n-bit integers which has at most k bits ON (bits 1), where 0 &lt; n &lt;= 32 and 0 &lt;= k &lt;= n. For example, if n = 4 and k = 2 then these numbers are (in binary digits): 0000, 0001, 0010, 0100, 1000, 0011, 0101, 0110, 1001, 1010, 1100. The order in which these numbers are looped through is not important, but each is visited only once.</p>
  
  <p>Currently I am using this straightforward algorithm:</p>
  
  <pre><code>for x = 0 to (2^n - 1)
      count number of bits 1 in x
      if count &lt;= k
          do something with x
      end if
  end for
  </code></pre>
  
  <p>I think this algorithm is inefficient because it has to loop through too many numbers. For example, if n = 32 and k = 2 then it has to loop through 2^32 numbers to find only 529 numbers (which have &lt;= 2 bits 1).</p>
  
  <p>My question is: is there any more efficient algorithm to do this?</p>