我需要生成一個隨機數，但需要從具有相同設置比特數的一組二進制數中選擇。例如。選擇一個正好爲2位的隨機字節值...使用固定比特數生成隨機數的最有效方法
00000000 - no
00000001 - no
00000010 - no
00000011 - YES
00000100 - no
00000101 - YES
00000110 - YES
...
=> Set of possible numbers 3, 5, 6...
請注意，這是一組簡化的數字。想想更多的是「選擇一個隨機的64位數字，正好設置了40位」。集合中的每個數字必須具有相同的可能性。
從所有位位置的集合中隨機選擇，然後設置這些位。
實施例中的Python：
def random_bits(word_size, bit_count):
number = 0
for bit in random.sample(range(word_size), bit_count):
number |= 1 << bit
return number
運行的10倍以上的結果：
0xb1f69da5cb867efbL
0xfceff3c3e16ea92dL
0xecaea89655befe77L
0xbf7d57a9b62f338bL
0x8cd1fee76f2c69f7L
0x8563bfc6d9df32dfL
0xdf0cdaebf0177e5fL
0xf7ab75fe3e2d11c7L
0x97f9f1cbb1f9e2f8L
0x7f7f075de5b73362L
這是另一個在實踐中非常簡單且相當快的選項。
choose a bit at random
if it is already set
do nothing
else
set it
increment count
end if
重複，直到計數等於您想要設置的位數。
當您想要設置的位數（稱爲k）超過字長的一半（稱爲N）時，這隻會很慢。在這種情況下，使用算法來設置N - k位，然後翻轉結果中的所有位。
我敢打賭，這裏的預期運行時間是相當不錯的，儘管我現在太懶惰/愚蠢的計算它。但我可以將它限制爲小於2 * k ...獲得「正面」的硬幣翻轉的預期次數是兩次，並且這裏的每次迭代都有超過1/2的成功機率。
如果你沒有Python的random.sample的方便，你可以用C採用了經典的順序採樣算法做到這一點：
unsigned long k_bit_helper(int n, int k, unsigned long bit, unsigned long accum) {
if !(n && k)
return accum;
if (k > rand() % n)
return k_bit_helper(n - 1, k - 1, bit + bit, accum + bit);
else
return k_bit_helper(n - 1, k, bit + bit, accum);
}
unsigned long random_k_bits(int k) {
return k_bit_helper(64, k, 1, 0);
}
以上將產生的成本佔據成本隨機數字（在其他解決方案中也是如此）。如果你有一個良好的批處理，你可以優化一下：例如，因爲你知道隨機數將在穩定遞減的範圍內，所以你可以得到n到n-3的隨機數，通過獲得一個範圍內的隨機數0..(n * (n - 1) * (n - 2) * (n - 3))然後提取所述個體隨機數：
r = randint(0, n * (n - 1) * (n - 2) * (n - 3) - 1);
rn = r % n; r /= n
rn1 = r % (n - 1); r /= (n - 1);
rn2 = r % (n - 2); r /= (n - 2);
rn3 = r % (n - 3); r /= (n - 3);
的n最大值是推測64或2 ，所以上述產物的最大值是一定小於2 。事實上，如果你使用64位的prng，你可以從中提取多達10個隨機數。但是，除非你知道你使用的prng產生獨立的隨機位，否則不要這樣做。
關於將長隨機數分成較小範圍的提示本身值得記住。 – izb
我發現了一個優雅的解決方案：隨機二分法。
想法是，平均：
C代碼用gcc編譯（具有__builtin_popcountll）：
#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
/// Return a random number, with nb_bits bits set out of the width LSB
uint64_t random_bits(uint8_t width, uint8_t nb_bits)
{
assert(nb_bits <= width);
assert(width <= 64);
uint64_t x_min = 0;
uint64_t x_max = width == 64 ? (uint64_t)-1 : (1UL<<width)-1;
int n = 0;
while (n != nb_bits)
{
// generate a random value of at least width bits
uint64_t x = random();
if (width > 31)
x ^= random() << 31;
if (width > 62)
x ^= random() << 33;
x = x_min | (x & x_max); // x_min is a subset of x, which is a subset of x_max
n = __builtin_popcountll(x);
printf("x_min = 0x%016lX, %d bits\n", x_min, __builtin_popcountll(x_min));
printf("x_max = 0x%016lX, %d bits\n", x_max, __builtin_popcountll(x_max));
printf("x = 0x%016lX, %d bits\n\n", x, n);
if (n > nb_bits)
x_max = x;
else
x_min = x;
}
return x_min;
}
通常達到的位的請求的數目，需要小於10環（並用運氣它可以採取2個或3循環）。即使特殊情況會更快，邊角情況（nb_bits = 0,1，寬度1，寬度）仍在工作。結果
例子：
x_min = 0x0000000000000000, 0 bits
x_max = 0x1FFFFFFFFFFFFFFF, 61 bits
x = 0x1492717D79B2F570, 33 bits
x_min = 0x0000000000000000, 0 bits
x_max = 0x1492717D79B2F570, 33 bits
x = 0x1000202C70305120, 14 bits
x_min = 0x0000000000000000, 0 bits
x_max = 0x1000202C70305120, 14 bits
x = 0x0000200C10200120, 7 bits
x_min = 0x0000200C10200120, 7 bits
x_max = 0x1000202C70305120, 14 bits
x = 0x1000200C70200120, 10 bits
x_min = 0x1000200C70200120, 10 bits
x_max = 0x1000202C70305120, 14 bits
x = 0x1000200C70201120, 11 bits
x_min = 0x1000200C70201120, 11 bits
x_max = 0x1000202C70305120, 14 bits
x = 0x1000200C70301120, 12 bits
width = 61, nb_bits = 12, x = 0x1000200C70301120
當然，你需要一個好的PRNG。否則，你可能面臨無限循環。
我還有一個基於枚舉的建議：選擇1到n之間的隨機數字i選擇k，並生成第i個組合。例如，對於n = 6，K = 3種的20種組合是：
000111
001011
010011
100011
001101
010101
100101
011001
101001
110001
001110
010110
100110
011010
101010
110010
011100
101100
110100
111000
比方說，我們隨機選擇組合7號我們首先檢查它是否在最後的位置有一個1：有，因爲前10（5選2）組合有。然後我們遞歸地檢查剩餘的位置。下面是一些C++代碼：
word ithCombination(int n, int k, word i) {
// i is zero-based
word x = 0;
word b = 1;
while (k) {
word c = binCoeff[n - 1][k - 1];
if (i < c) {
x |= b;
--k;
} else {
i -= c;
}
--n;
b <<= 1;
}
return x;
}
word randomKBits(int k) {
word i = randomRange(0, binCoeff[BITS_PER_WORD][k] - 1);
return ithCombination(BITS_PER_WORD, k, i);
}
要快，我們使用預先計算二項式係數binCoeff。函數randomRange返回兩個邊界之間的隨機整數（包含）。
我做了一些計時（source）。使用C++ 11默認隨機數生成器，大部分時間都用於生成隨機數。那麼這個解決方案是最快的，因爲它使用絕對最小數量的隨機比特。如果我使用快速隨機數發生器，那麼mic006的解決方案是最快的。如果知道k非常小，最好只是隨機設置位，直到設置了k。
爲設定位選擇'N'個隨機位置。 –