c - 根据函数F(N)=等级查找十进制数的等级

我发现了这个问题here，但这不是我想要的答案。因此，再次发布。

形式的功能:

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解决方案？

最佳答案

是的，有一个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 -th设置为小于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循环中进行了测试，以检查是否有任何不匹配的错误。

检查输出here。