7

ここでこの質問を見つけましたが、これは私が探している答えではありません。というわけで再投稿。

次の形式の関数:

F( N ) = rank

N10 進数表現の数値が与えられると、そのランクは次のように与えられることを意味します。

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)k0, ..., p-1knk == 1kpnn - 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を表すために必要なビット数を見つけます。2進表現では、数値は次のように構成できます。

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

さて、n上記の方程式で(または数値の2進表現のビット数)を見つけるために、それがであると仮定することができますfloor(log2(N)) + 1。たとえば、任意の数を考えてみましょう。たとえば、118floor(log2(118))+ 1=7ビットで表すことができます。

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

上記の式はのみO(1)です。ここで、数値の2進表現に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まず、は、数値を表すために必要なビット数であり、数値のビット表現では1の数であると仮定しますc。したがって、ランクは次のように与えられます。

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

編集:DSMによって提案されたように、正しいランクを見つけるためにロジックを修正しました。アイデアは、順列からすべての不要な数を削除することです。したがって、このコードを追加しました:

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

そして、上記のalogrithmは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常にです。10log2(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 ビット加算などを行います。より長いマスクと 1 つの追加ステップを使用して、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 に答える