ここでこの質問を見つけましたが、これは私が探している答えではありません。というわけで再投稿。
次の形式の関数:
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 ソリューションはありますか?
はい、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不一致が見つからずに間違いをチェックするためのループでテストされました。
ここで出力を確認してください。
それは、組み合わせと順列の技術によって解決することができます。
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)
これは、ステップごとに複数の加算を並行して実行するかなり効率的な 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;
}