c - ビットの位置に基づいて値をランダムに選択する方法

Question

ビット位置に基づいて値を選択する方法はありますか。問題のステートメントは次のとおりです:- 16 ビット位置の場合、任意のビットを設定できます。たとえば、1,4,6,7,11,13 ビットを設定すると、マスクは次のようになります:-

Bit Positons 0 0 1 0 1 0 0 0 1 1 0 1 0 0 1 0

ここで、このビット マスクに基づいて値をランダムに選択する必要があります。1 ビットのみが設定されているため、可能な値は次のようになります。

4 :0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 を選択する場合

For Selecting 7: 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0

しかし、この値をランダムに選択する必要があるため、このようにすることを考えました

1) ビット マスクに基づいて配列を作成します。16 ビットの場合、配列には 16 個の一意の値が含まれます。

2) 次に、配列の位置に対して rand 操作を実行して、配列のインデックスを取得します。

3) その配列インデックスの値を使用します。

それを行うより良い方法はありますか？

Answer 1

ちょうど1 つのビット セットが必要な場合は、再試行ループまたは次のようなものを使用できます: (適切な定義を追加し、場合によっては の特殊なケースを追加しますmask == 0)

while (mask)
{
    array[i++] = mask & -mask;
    mask &= mask - 1;
}
return array[rand_in_range(0, i)];

whererand_in_range(a, b)は範囲 [a, b> の乱数を返す関数です (ほとんどのテストでは正しいように見えますrand_in_rangeが、実装の 99%は正しくないことに注意してください。最悪の種類のバグです)。