3

我正在尝试编写一个基于随机生成的指令集的简单虚拟机。在 C 中，生成包含N 位集的随机位掩码的最佳方法是什么（与生成随机整数不同，因为不能保证其中设置了 N 位）。我需要它适用于 16 位和 32 位整数。

编辑：它必须恰好设置 N 位。正是。不多。而且不少。正好设置了 N 位。它不必非常安全，也不必从宇宙噪声中获取熵。它必须是伪随机的。

这就是我真正想要实现的目标：

uint32_t rand_bits_32(size_t reqBits)
{
    /* blah */
}

uint16_t rand_bits_16(size_t reqBits)
{
    /* blah */
}

extern char *int2bin(uint32_t n, char *buf);

uint16_t gen_mask_16_excl_32(uint32_t* exclude, size_t exclude_count, size_t bits_required)
{
    uint32_t ret = 0;

    while (1) {
        bool has = false;
        ret = (uint32_t)rand_bits_16(bits_required);

        for (size_t i = 0; i < exclude_count; i++) {
            if (ret & (uint32_t)exclude[i]) {
                has = true;
                break;
            }
        }

        if (!has) {
            break;
        }

        has = false;
    }

    return ret;
}

uint32_t gen_mask_32(uint32_t* exclude, size_t exclude_count, size_t bits_required)
{
    uint32_t ret = 0;

    while (1) {
        bool has = false;
        ret = rand_bits_32(bits_required);

        for (int i = 0; i < exclude_count; i++) {
            if (ret & (uint32_t)exclude[i]) {
                has = true;
                break;
            }
        }

        if (!has)
            break;

        has = false;
    }

    return ret;
}

我生成随机位，然后AND对现有位掩码进行暴力破解，直到没有位匹配，因此我可以生成具有 N 个位的位掩码，并且没有其他位掩码共有的位。是的，这段代码很糟糕，在 x86_64 上会中断。

4

4 回答 4

4

我根据 Steve Emmerson 的想法松散地写了一个 C99 实现。你可以看到它在 ideone 运行。

除非出现任何错误，randto()否则shuffle()这应该可以满足您的要求。

#include <stdint.h>
#include <stdlib.h>

static int randto(int n) {
  int r;
  int maxrand = (RAND_MAX / n) * n;
  do r = rand(); while (r >= maxrand);
  return r % n;
}

static void shuffle(unsigned *x, size_t n) {
  while (--n) {
    size_t j = randto(n + 1);
    unsigned tmp = x[n];
    x[n] = x[j];
    x[j] = tmp;
  }
}

uint16_t nrand16(int n) {
  uint16_t v = 0;
  static unsigned pos[16] = {0, 1,  2,  3,  4,  5,  6,  7,
                             8, 9, 10, 11, 12, 13, 14, 15};
  shuffle(pos, 16);
  while (n--) v |= (1U << pos[n]);
  return v;
}

uint32_t nrand32(int n) {
  uint32_t v = 0;
  static unsigned pos[32] = { 0,  1,  2,  3,  4,  5,  6,  7,
                              8,  9, 10, 11, 12, 13, 14, 15,
                             16, 17, 18, 19, 20, 21, 22, 23,
                             24, 25, 26, 27, 28, 29, 30, 31};
  shuffle(pos, 32);
  while (n--) v |= (1U << pos[n]);
  return v;
}
于 2013-03-28T22:08:28.693 回答
1

像这样的东西可能会起作用

#include <stdlib.h>
#include <string.h>

unsigned long set_bits(
    unsigned size,       /** [in] Size of the integer in bits: 16, 32 */
    const unsigned nbits)/** [in] Number of bits to be set */
{
    unsigned pos[nbits];
    unsigned long result = 0;

    srand(time(NULL));

    for (unsigned i = 0; i < size; i++)
        pos[i] = i;

    for (unsigned i = 0; i < nbits; i++) {
        unsigned j = rand()%size--;

        result |= 1 << pos[j];

        (void)memmov(pos+j, pos+j+1, size-j);
    }

    return result;
}

我没有测试过这个。

于 2013-03-28T21:19:03.170 回答
1

我最终选择了自己的实现。它似乎工作。

static bool prob(double probability)
{
    return rand() <  probability * ((double)RAND_MAX + 1.0);
}

uint32_t count_set_bits(uint32_t i)
{
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

uint32_t gen_mask_excl_32(size_t bits, uint32_t* exclude, size_t exclude_count, size_t bits_required)
{
    uint32_t excl_mask = 0;

    size_t mask_bit_count;
    size_t rem_bit_count;

    uint32_t out_mask = 0;

    if (exclude_count == 0) {
        /* pass */
        if (exclude != NULL) {
            abort();
        }
    }
    else {
        for (size_t i = 0; i < exclude_count; i++) {
            excl_mask |= exclude[i];
        }
    }

    mask_bit_count = count_set_bits(excl_mask);
    if (mask_bit_count == bits) {
        /* overflow! */
        abort();
    }
    rem_bit_count = bits - mask_bit_count;

retry:
    for (size_t i = 0; i < bits; i++) {
        unsigned re;

        if (( 1 << i ) & excl_mask || ( 1 << i ) & out_mask) {
            /* bit already set, skip */
            continue;
        }

        re = prob((double)1 / (double)rem_bit_count);
        if (re) {
            out_mask = ( 1 << i ) | out_mask;
            bits_required--;
        }

        if (bits_required == 0) {
            break;
        }
    }

    /* still stuff left */
    if (bits_required) {
        goto retry;
    }

    return out_mask;
}

uint16_t gen_mask_16_excl_32(uint32_t* exclude, size_t exclude_count, size_t bits_required)
{
    return (uint16_t)gen_mask_excl_32(16, exclude, exclude_count, bits_required);
}

uint32_t gen_mask_32(uint32_t* exclude, size_t exclude_count, size_t bits_required)
{
    return (uint32_t)gen_mask_excl_32(32, exclude, exclude_count, bits_required);
}

uint32_t rand_bits_32(size_t reqBits)
{
   return gen_mask_32(NULL, 0, reqBits);
}

uint16_t rand_bits_16(size_t reqBits)
{
    return gen_mask_16_excl_32(NULL, 0, reqBits);
}
于 2013-03-29T01:30:26.073 回答
0

如果 RAN32() 返回带有随机位的随机 uint32_t，则下面的代码应该可以完成工作。这样的功能应该由您常用的随机数生成器提供。

uint32_t fixed_nb_bits(int b)
{
    if ( b > 31 )
        return ~0;
    uint32_t n = 0;
    while ( b > 0 )
    {
        uint32_t x = 1 << ( RAN32() % 32 );
        if (!( n & x ))
        {
            n += x;
            --b;
        }
    }
    return n;
}

但是，此代码对于 ( b > 16 ) 不是最佳的，在这种情况下，最好只反转：

~fixed_nb_bits(32-b)
于 2014-10-23T14:50:23.747 回答