根据 1 的数量查找数字的排名

令 f(k) = y 其中 k 是非负整数递增序列中的第 y 个数 其二进制表示形式中的 1 数量与 k 相同，例如f(0) = 1、f(1) = 1、f(2) = 2、f(3) = 1、f(4) = 3、f(5) = 2、f(6) = 3 等等。给定 k >= 0，计算 f(k)

我们很多人都看过这个问题

此问题的 1 个解决方案是根据 1 的数量对数字进行分类，然后找到排名。我确实找到了一些通过这种方式进行的模式，但这将是一个漫长的过程。谁能建议我一个更好的解决方案？

这是一个计数问题。我认为，如果您考虑到这一点，您可以做得比逐字枚举值并检查它们有多少位要好得多。

考虑数字 17。二进制表示为 10001。1 的数量为 2。通过（在本例中）将 1 重新分配到四个低位中的任意一个，我们可以得到具有两个 1 的较小数字。 4选2就是6，所以17应该是二进制表示中第7个有2个1的数字。我们可以检查这个...

   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

我们是对的。概括这个想法，你应该得到一个有效的函数，你只需computek 的等级。

编辑：泛化提示 17的特殊之处在于，如果不考虑高位，则该数的秩为1；也就是说，f(z) = 1，其中 z 是除高阶位之外的所有值。对于情况并非如此的数字，如何解释在不移动高位的情况下可以获得更小的数字的事实？