发现一些秩上的1的数目的基础 [英] Find rank of a number on basis of number of 1's

问题描述

设f（k）的= y其中k是一个非负整数的日益增加的序列中的第y数
在其二进制重新presentation为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）

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的解决了这个问题1的数量的基础上分类编号，然后找到rank.i确实发现一些模式通过这样的方式去，但是这将是一个漫长的过程。任何人都可以建议我一个更好的解决方案？

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?

推荐答案

这是一个计数的问题。我认为，如果你考虑到这一点接近它，你可以做的比字面上枚举值，并检查他们有多少位有更好的。

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.

考虑数17.二进制重新presentation是10001 1秒的数量为2，我们可以通过用两个1变小的数字（在本例中）重新分发1s至任何四个低的阶位。 4选2为6，所以17应该是2个1的二进制重新presentation第7号。我们可以检查此...

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

和我们是正确的。概括这个想法，你应该得到一个有效的功能，您只需计算的k的行列。

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

编辑：提示泛化
17是在特殊的，如果你不考虑高位，数量已排名1;即f（Z）= 1，其中，z是除了较高阶位的一切。对于数字的地方，这是不是这样的，你怎么能解释这个事实，你可以得到更小的数字，而无需移动高位？

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?

这篇关于发现一些秩上的1的数目的基础的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！