根据函数F(N)= rank找到十进制数的等级

Question

我在这里找到了这个问题,但这不是我要找的答案.因此,再次发布.

形式的功能:

F( N ) = rank

表示给定N十进制表示的数字,其等级为:

Starting from 0 to N, how many numbers are there with same number of set bits in its
binary representation.

我将通过一个例子来说明问题.

N = 6 ( 0110 )
Its rank is 3.
1. 3 ( 0011 )
2. 5 ( 0101 )
3. 6 ( 0110 )

现在,给出一个数字,找到它的排名.

显而易见的方法是从0开始并检查每个数字的设置位数N-1.

问题是:

有没有logN解决方案？

Answer 1

是的,有一个log n解决方案.

我们n有k设定,最显著位位置是位p(开始计数为0的位置,所以2^p <= n < 2^(p+1)).然后还有pCk(二项式系数choose(p,k))将位置k于位置的方法0, ..., p-1,所有这些都给出k了具有小于的精确设置位的数字n.如果k == 1,就是这样,否则仍然存在k设置位和p第 - 位设置的数字小于n要考虑的数字.这些可以通过确定等级来计算n - 2^p.

代码(不是最优的,做一些不必要的重新计算,并不是它可以做的所有以避免溢出):

unsigned long long binom(unsigned n, unsigned k) {
    if (k == 0 || n == k) return 1;
    if (n < k) return 0;
    if (k > (n >> 1)) k = n-k;
    unsigned long long res = n, j;
    // We're not doing all we can to avoid overflow, as this is a proof of concept,
    // not production code.
    for(j = 2; j <= k; ++j) {
        res *= (n+1-j);
        res /= j;
    }
    return res;
}

unsigned popcount(unsigned long long n) {
    unsigned k = 0;
    while(n) {
        ++k;
        n &= (n-1);
    }
    return k;
}

unsigned long long rank(unsigned long long n) {
    if (n == 0) return 1;
    unsigned p = 0, k = popcount(n);
    unsigned long long mask = 1,h = n >> 1;
    while(h > 0) {
        ++p;
        h >>= 1;
    }
    mask <<= p;
    unsigned long long r = binom(p,k);
    r += rank(n-mask);
    return r;
}

测试循环0 <= n < 10^8以检查错误,没有发现任何不匹配.

在这里检查输出.