がランダムビット機能

Question

与えられたランダムintはあなたが返すint randBit()機能を与えられていると仮定し、生成、均一に分布して、0または1

はrandNumber（int型の最大値）関数を記述します。

これは私の実装ですが、正しいとは証明できません。

// max number of bits 
    int i = (int)Math.floor(Math.log(max)/Math.log(2)) + 1; 

    int ret = randBit(); 
    while (i-- > 0) { 
     ret = ret << 1 | randBit(); 
    } 

    return ret; 

私が持っていた基本的な考え方は、

• は数その後、
• 継続的に連結することによって番号を生成中に存在するビットの数を見つけることであるLSBビット長は

を満たされるまで

Answer 1

intをランダムビットで埋めるアプローチは、私の意見では正しい方法です。しかし、あなたのアルゴリズムは唯一最大の2の累乗であると、ループ内のいずれかでオフになっているとき、私はこの変更をお勧めしたい作品以来：

// max number of bits 
int i = (int)Math.floor(Math.log(max)/Math.log(2)) + 1; 

int rnd = 0; 
int mask = 1; 

while (i-- > 0) { 
    rnd = rnd << 1 | randBit(); 
    mask <<= 1; // or: mask *= 2 
} 
double q = (double)rnd/mask; // range is [0, 1) 
return (int)((max + 1) * q); 

さんはこれを見てみましょう：

iます常にmaxが占有するビット数と等しくなければなりません。ループが終了すると、rndは0または1でランダムに埋められたビット数を含み、mask-1は1で満たされたビット数を含みます。したがって、rndとmask-1の商が0と1との間に均等に分布していると仮定することは安全です。maxを乗じると0〜maxの範囲の結果が浮動/実数の値として均等に分布します。

この結果は整数にマッピングする必要があります。もちろん、これらの値を一様に分散したい場合もあります。ここで唯一のキャッチは1です。rndとmask-1の商がちょうど1の場合、希望の結果範囲にスケーリングするときに問題を引き起こすエッジケースがあります。0 .. max-1の値が均一に分布しますが、maxはまれな例外です。

この条件を処理するには、商が0から1の範囲になるように1 となるように商を構築する必要があります。これはrnd/maskによって達成されます。この範囲は、max+1を乗算してintにキャストすることで、均一に広げられた整数0 .. maxに簡単にマッピングできます。