Generate a random integer with N bits?

Question

I'm trying to write a simple virtual machine that is based off a randomly generated instruction set. What would be the best way, in C, of generating a random bitmask that would contain N bits set (not the same as generating a random integer, since that is not guaranteed to have N bits set in it). I need this to work for both 16 and 32 bit integers.

Edit: It has to have exactly N bits set. Exactly. Not more. And not less. Exactly N bits set. It doesn't have to be super secure, and it doesn't have to get it's entropy from cosmic noise. It just has to be pseudorandom.

This is what I'm actually trying to achieve:

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;
}

I generate random bits and then bruteforce AND them against an existing bitmask until none of the bits match, so I can generate bitmasks with N numbers of bits and that have none of the bits that are common with the other bitmasks. And yes, this code is horrible and breaks on x86_64.

Answer 1

I wrote a C99 implementation loosely based on Steve Emmerson's idea. You can see it running at ideone.

Barring any mistakes in randto() and shuffle() this should do what you want.

#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;
}

Answer 2

Something like this might work

#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;
}

I haven't tested this.

Answer 3

I ended up going with my own implementation. It seems to work.

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);
}

Answer 4

The code below should do the work, provided RAN32() returns a random uint32_t with random bits. Such a function should be provided by your usual Random Number generator.

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;
}

This code however is not optimal for ( b > 16 ), where it becomes better to just invert:

~fixed_nb_bits(32-b)