我找到了一个优雅的解决方案:随机二分法。
平均而言,想法是:
- 并且用一个随机数除以 2 设置的位数,
- 或添加 50% 的设置位。
用 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。否则你可能会面临一个无限循环。