我需要生成一个随机数，但它需要从一组具有相同位数的二进制数中选择。例如，选择一个恰好设置了 2 位的随机字节值...
00000000 - no
00000001 - no
00000010 - no
00000011 - YES
00000100 - no
00000101 - YES
00000110 - YES
...
=> Set of possible numbers 3, 5, 6...
请注意，这是一组简化的数字。更多地考虑“选择一个恰好设置了 40 位的随机 64 位数字”。集合中的每个数字必须同样可能出现。
从所有位位置的集合中进行随机选择，然后设置这些位。
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
我找到了一个优雅的解决方案：随机二分法。
平均而言，想法是：
用 gcc 编译的 C 代码（要有 __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,width-1,width) 也可以正常工作。
结果示例：
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。否则你可能会面临一个无限循环。
假设要设置的位数是 b，字长是 w。我将创建一个长度为 w 的向量 v，其中第一个 b 值设置为 1，其余设置为 0。然后只是随机播放 v。
这是另一个在实践中非常简单且相当快的选项。
choose a bit at random
if it is already set
do nothing
else
set it
increment count
end if
重复直到 count 等于您要设置的位数。
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);
}
上述成本将主要由生成随机数的成本决定（在其他解决方案中也是如此）。如果您通过批处理获得了良好的 prng，则可以对其进行一些优化：例如，由于您知道随机数将处于稳步下降的范围内，因此您可以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大概是642 6，所以上面乘积的最大值肯定小于2 24。实际上，如果您使用 64 位 prng，您可以从中提取多达 10 个随机数。但是，除非您知道您使用的 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返回两个边界（包括）之间的随机整数。
我做了一些时间安排（来源）。使用 C++11 默认随机数生成器，大部分时间都花在生成随机数上。那么这个解决方案是最快的，因为它使用了尽可能少的随机位数。如果我使用快速随机数生成器，那么 mic006 的解决方案是最快的。如果k已知非常小，最好只是随机设置位，直到k被设置。
不完全是算法建议，只是在 JavaScript 中找到了一个非常巧妙的解决方案，可以使用 ArrayBuffer 直接从 Math.random 输出位中获取随机位。
//Swap var out with const and let for maximum performance! I like to use var because of prototyping ease
var randomBitList = function(n){
var floats = Math.ceil(n/64)+1;
var buff = new ArrayBuffer(floats*8);
var floatView = new Float64Array(buff);
var int8View = new Uint8Array(buff);
var intView = new Int32Array(buff);
for(var i = 0; i < (floats-1)*2; i++){
floatView[floats-1] = Math.random();
int8View[(floats-1)*8] = int8View[(floats-1)*8+4];
intView[i] = intView[(floats-1)*2];
}
this.get = function(idx){
var i = idx>>5;//divide by 32
var j = idx%32;
return (intView[i]>>j)&1;
//return Math.random()>0.5?0:1;
};
this.getBitList = function(){
var arr = [];
for(var idx = 0; idx < n; idx++){
var i = idx>>5;//divide by 32
var j = idx%32;
arr[idx] = (intView[i]>>j)&1;
}
return arr;
}
};