问根据1的个数计算一个数的排名

EN

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

以数字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

我们是对的。推广这个想法，你应该得到一个有效的函数，你可以简单地计算k的秩。

编辑:泛化17的提示是特殊的，因为如果不考虑高位，数字的秩为1；即，f(z) =1，其中z是除高位以外的所有东西。对于不是这样的数字，你如何解释这样一个事实，即你可以在不移动高位的情况下获得更小的数字？

f( k )是小于或等于k的整数，它们的二进制表示中的1的数量与k相同。

例如，k需要m个比特，即k = 2^(m-1) + a，其中a < 2^(m-1)。具有与k相同位数的小于2^(m-1)的整数的数量是choose(m-1, bitcount(k))，因为您可以在m-1最低有效位之间自由地重新分配这些位。

大于或等于2^(m-1)的整数具有与k(即1)相同的最高有效位，因此它们是f(k - 2^(m-1))。这意味着f(k) = choose(m-1, bitcount(k)) + f(k-2^(m-1))。

参见"Efficiently Enumerating the Subsets of a Set"。请看表3，“银行家序列”。这是一种生成所需序列的方法(如果您颠倒了位顺序)。只需对具有K位的字运行K次迭代。论文中包含了生成它的代码。