バイナリ表現が指定された整数とちょうどkの位置が異なるカウント整数

Question

4つの整数a≤b≤cとkが与えられた場合、バイナリ表現が正確にk位置が異なる[a、c] Bのそれ？ a、b、cは約30ビットです。

Answer 1

bのバイナリreprを書き、そのビットを反転して境界に違反していないかどうかを確認します。 a、bが30ビットの場合、kが妥当である限り、シェルスクリプトやCプログラムを記述することは禁忌ではありません。

Answer 2

aとcの間のすべての値を明示的に列挙して、値ごとにいくつのビットが異なるかをチェックするのはなぜですか？この情報理論の技術用語は、 http://en.wikipedia.org/wiki/Hamming_distance

Answer 3

であり、bと正確にkの位置が異なり、多くとも30ビットで書かれた合計数はbinomial(30, k)である。この数は、k = 15で最大値がbinomial(30, 15) = 155117520なので、aからenumaratingする方が良いですが、依然として多くなる可能性があります。しかし、kが小さければそれは方法です - ちょうどkビットで異なるこれらの数をすべて列挙し、それらがaとcの間にあるかどうかをチェックしてください。 これが遅すぎる場合は、より賢明に実行する必要があります。たとえば、aとcの最高ビットが同じ場合、このビットを設定する必要があるため、可能性を減らすことができます。

Answer 4

与えられたa、b、cの数とkのすべての値を計算する必要がある場合は、xor'edの差のビット数を反復して数えることをお勧めします。

for (int i = a; i <= c; i++) { 
    int d = i^b; 
    int k = 0; 
    while (d != 0) { 
     k++; 
     d &= (d - 1); 
    } 
    counts[k]++; 
} 

これを簡単に並列化することもできます。あなたは、スレッドごとにカウントを別々にして、総計を得るためにそれらをすべて最後に追加する必要があります。

このアルゴリズムの並列バージョンは、私のマシンで3.7秒かかりました。

編集：実際には、列挙せずにカウントを取得する方法があります。ここでは、（a、b、c）=（17,25,29）、またはバイナリ（10001,11001,11101）の基本的な考え方を示します。まず、範囲11000〜11011にはbが含まれ、（a、c）にも完全に含まれていることに注意してください。したがって、これらの2^2値は、各カウントにchoose（2、k）を与えます。次の間隔は10100〜10111です。この範囲の数値はすべてbと少なくとも2ビット異なるので、k番目のcountにchoose（2、k-2）を与えます。 （a、c）に完全に含まれる次の間隔は、choose（1、k-1）などに寄与する10010〜10011です。また、上向きに数えなければなりません。

2回目の編集：これを実装することに抵抗できませんでした。 10億回の合計時間：0.004ms ...