根据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的数量对数字进行分类然后找到rank.i确实找到了一些模式，但这将是一个漫长的过程。 有谁能建议我一个更好的解决方案？
这是一个计数问题。 我认为，如果你考虑到这一点，你可以做得比在字面上枚举值和检查它们有多少位要好得多。
考虑数字17.二进制表示是10001.1的数量是2.我们可以得到两个1的较小数字（在这种情况下）将1重新分配给四个低位中的任何一个。 4选择2是6，所以17应该是第7个数字，在二进制表示中有2个。 我们可以查一下……
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的整数，其二进制表示中具有与k相同数量的1。
例如，k需要m比特，即k = 2^(m-1) + a ，其中a < 2^(m-1) 。 选择小于2^(m-1)且与k具有相同位数的整数的数量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)) 。
请参阅“有效枚举集合的子集” 。 请看表3，“银行家序列”。 这是一种精确生成所需序列的方法（如果反转位顺序）。 只需用K位运行K迭代。 该文件中包含生成它的代码。