根据1的数量查找数字的等级

Question

设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确实找到了一些模式,但这将是一个漫长的过程.谁能建议我一个更好的解决方案？

Answer 1

这是一个计数问题.我认为,如果你考虑到这一点,你可以做得比在字面上枚举值和检查它们有多少位要好得多.

考虑数字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是除高阶位之外的所有内容.对于不是这种情况的数字,您如何解释在不移动高位的情况下可以获得较小数字的事实？