0

I am provided with maximum number of bits N

I want to generate the sequence of "No. of set bits, in increasing order starting from 0 upto maximum bits N"

for eg for something like N=3

000

001 010 100

011 110 101

111

Here relative ordering between numbers ,with equal no. of set bits is unimportant ,so printing '100' before '001' doesn't alter correctness

My solution to this has been

i=0;
while(i<n)
{
  num=0;
  for(int j=0;j<=i;j++)
    num+=math.pow(2,j);

  while(num<pow(2,n))
    {
     print n;
     num<<1;

    }   
  i++;


}

I think there exist a much faster/efficient way to achieve this ,using less costly operators.How can i do it efficiently/faster?

Samaksh Yadav
  • 17
  • 6
  • You can use the good old "generate all patterns with k bits set" (search, it's on SO several times), and then loop over k as well. And obviously you can replace that `pow(2, i)`. – harold Jan 15 '16 at 12:49
  • 1
    One quick speedup is to replace `pow(2,j)` with `1< – AShelly Jan 15 '16 at 19:29

0 Answers0