7

我在这里找到了这个问题，但这不是我正在寻找的答案。因此，再次发布。

形式的一个功能： 

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

4

3 回答 3

7

是的，有一个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以检查错误，但未发现任何不匹配。

在此处检查输出。

于 2012-09-03T18:34:49.980 回答
0

它可以通过组合和排列技术来解决。

F(N) = 等级

首先找到表示 N 所需的位数。在二进制表示中，数字可以构造如下：

N = cn 2^n + .... + c3 2^2 + c2 2^1 + c1 2^0

现在，为了n在上述等式中找到（或数字的二进制表示中的位数），我们可以假设它将是floor(log2(N)) + 1。例如，考虑任何数字，假设118它可以用 floor(log2(118)) + 1 = 7 位表示。

n = floor(log2(118)) + 1;

上式只有O(1). 现在，我们需要找出一个数字的二进制表示中有多少个 1。考虑一个伪代码来完成这项工作：

function count1(int N) {
    int c = 0;
    int N' = N;

    while(N' > 0) {
       N' -= 2^(floor(log2(N')));
       c++;
    }
}

上面的伪代码是O(logN). 我在 MATLAB 中编写了小脚本来测试我上面的伪代码，结果如下。

count1(6)   = 2
count1(3)   = 2
count1(118) = 5

完美，现在我们有了这些位的位数和 1 的数量。现在，可以应用简单的组合和排列来找到数字的秩。首先让我们假设，n是表示数字所需的位数，并且c是数字的位表示中的 1 的数量。因此，排名将由以下方式给出：

r = n ! / c ! * (n - c) !

编辑：正如 DSM 所建议的，我已经更正了逻辑以找到正确的 RANK。想法是从排列中删除所有不需要的数字。所以添加了这段代码：

for i = N + 1 : 2^n - 1
    if count(i) == c
       r = r - 1;
    end
end

我编写了一个 MATLAb 脚本来使用上述方法查找数字的等级：

function r = rankN(N)

n = floor(log2(N)) + 1;
c = count(N);
r = factorial(n) / (factorial(c) * factorial(n - c));
% rejecting all the numbers may have included in the permutations 
% but are unnecessary.
for i = N + 1 : 2^n - 1
    if count(i) == c
       r = r - 1;
    end
end

function c = count(n)

c = 0;
N = n;
while N > 0
    N = N - 2^(floor(log2(N)));
    c = c + 1;
end

上面的算法是O(1) + O(logN) + O(1) = O(logN)。输出是：

>> rankN(3)

ans =

     1

>> rankN(4)

ans =

     3

>> rankN(7)

ans =

     1

>> rankN(118)

ans =

    18

>> rankN(6)

ans =

     3

注意：排名0始终是1因为上述方法将失败，0因为log2(0)未定义。

于 2012-09-03T19:12:27.343 回答
0

这是一个相当高效的 O(logN) 实现，每一步并行执行多个加法：

unsigned int countBits( unsigned int bits )
{
    bits = ( bits & 0x55555555 ) + ( ( bits >> 1 ) & 0x55555555 );
    bits = ( bits & 0x33333333 ) + ( ( bits >> 2 ) & 0x33333333 );
    bits = ( bits + ( bits >>  4 ) ) & 0x0f0f0f0f;
    bits += bits >>  8;
    return ( bits + ( bits >> 16 ) ) & 63;
}

它从 16 个 2 位加法开始，然后进行 8 个 4 位加法，依此类推。通过使用更长的掩码和一个额外的步骤，它可以扩展为使用 64 位整数：

unsigned int countBits( unsigned long long bits )
{
    bits = ( bits & 0x5555555555555555L ) + ( ( bits >> 1 ) & 0x5555555555555555LL );
    bits = ( bits & 0x3333333333333333L ) + ( ( bits >> 2 ) & 0x3333333333333333LL );
    bits = ( bits + ( bits >>  4 ) ) & 0x0f0f0f0f0f0f0f0fLL;
    bits += bits >>  8;
    bits += bits >> 16;
    return (unsigned int) ( bits + ( bits >> 32 ) ) & 127;
}
于 2012-09-03T19:39:13.177 回答