生成具有固定位数的随机数的最有效方法

Question

我需要生成一个随机数,但需要从具有相同数量的设置位的二进制数集中选择.例如,选择一个正好2位的随机字节值...

00000000 - no
00000001 - no
00000010 - no
00000011 - YES
00000100 - no
00000101 - YES
00000110 - YES
...

=> Set of possible numbers 3, 5, 6...

请注意,这是一组简化的数字.更多地考虑"选择一个正确的40位设置的随机64位数字".该组中的每个数字必须同样可能出现.

Answer 1

从所有位位置进行随机选择,然后设置这些位.

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

Answer 2

假设要设置的位数为 b，字长为 w。我将创建一个长度为 w 的向量 v，其中前一个 b 值设置为 1，其余设置为 0。然后对 v 进行随机播放。

Answer 3

我找到了一个优雅的解决方案:随机二分法.

想法是平均的:

• 并且随机数除以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,宽度-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

当然,你需要一个好的技巧.否则你可能面临无限循环.