Find rank of a number on basis of number of 1's

Question

Let f(k) = y where k is the y-th number in the increasing sequence of non-negative integers with the same number of ones in its binary representation as k, e.g. f(0) = 1, f(1) = 1, f(2) = 2, f(3) = 1, f(4) = 3, f(5) = 2, f(6) = 3 and so on. Given k >= 0, compute f(k)

many of us have seen this question

1 solution to this problem to categorise numbers on basis of number of 1's and then find the rank.i did find some patterns going by this way but it would be a lengthy process. can anyone suggest me a better solution?

Answer 1

This is a counting problem. I think that if you approach it with this in mind, you can do much better than literally enumerating values and checking how many bits they have.

Consider the number 17. The binary representation is 10001. The number of 1s is 2. We can get smaller numbers with two 1s by (in this case) re-distributing the 1s to any of the four low-order bits. 4 choose 2 is 6, so 17 should be the 7th number with 2 ones in the binary representation. We can check this...

   0 00000 -
   1 00001 -
   2 00010 -
   3 00011 1
   4 00100 -
   5 00101 2
   6 00110 3
   7 00111 -
   8 01000 -
   9 01001 4
  10 01010 5
  11 01011 -
  12 01100 6
  13 01101 -
  14 01110 -
  15 01111 -
  16 10000 -
  17 10001 7

And we were right. Generalize that idea and you should get an efficient function for which you simply compute the rank of k.

EDIT: Hint for generalization 17 is special in that if you don't consider the high-order bit, the number has rank 1; that is, f(z) = 1 where z is everything except the higher order bit. For numbers where this is not the case, how can you account for the fact that you can get smaller numbers without moving the high-order bit?