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

私はスティーブ・エマーソンのアイデアに基づいて大まかに 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 に答える