The most efficient method for generating a random number with a fixed number of bits

Question

I need to create a random number, but it must be selected from a set of binary numbers with an equal number of given bits. For example. select a random byte value accurate to 2 bits ...

00000000 - no 00000001 - no 00000010 - no 00000011 - YES 00000100 - no 00000101 - YES 00000110 - YES ... => Set of possible numbers 3, 5, 6... 

Please note that this is a simplified set of numbers. Think more about the strings "Choose a random 64-bit number accurate to 40 bits." Each number in the set should be equally likely.

Answer 1

Make a random selection from the set of all bit positions, then set these bits.

An example in 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 

Results above 10 times:

 0xb1f69da5cb867efbL 0xfceff3c3e16ea92dL 0xecaea89655befe77L 0xbf7d57a9b62f338bL 0x8cd1fee76f2c69f7L 0x8563bfc6d9df32dfL 0xdf0cdaebf0177e5fL 0xf7ab75fe3e2d11c7L 0x97f9f1cbb1f9e2f8L 0x7f7f075de5b73362L 

Answer 2

Let's say that the number of bits for the set is b, and the word size is w. I would create a vector v of length w with the first values ​​of b set to 1, and the rest equal to 0. Then just shuffle v.

Answer 3

I found an elegant solution: random dichotomy.

The idea is that on average:

• and with a random number divides by 2 the number of set bits,
• or adds 50% of the set bits.

C code to compile with gcc (for __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; } 

In general, less than 10 cycles are required to achieve the requested number of bits (and with luck, it can take 2 or 3 cycles). Corner cases (nb_bits = 0.1, width-1, width) work even if the special case is faster.

Example result:

 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 

Of course you need a good prng. Otherwise, you may encounter an infinite loop.

Answer 4

Here is another option that is very simple and fast enough in practice.

 choose a bit at random if it is already set do nothing else set it increment count end if 

Repeat until the count is equal to the number of bits you want to set.

It will only be slow if the number of bits you want to set (name k ) is more than half the word length (name it N ). In this case, use the algorithm to set the N - k bits, and then flip all the bits as a result.

I am sure that the expected time here is pretty good, although I'm too lazy / stupid to figure it out right now. But I can link it as less than 2 * k ... The expected number of coin flips to get the “heads” is two, and each iteration here has a chance of success of more than 1/2.

Answer 5

If you don’t have the convenience of Python random.sample , you can do it in C using the classic sequential fetch algorithm:

 unsigned long k_bit_helper(int n, int k, unsigned long bit, unsigned long accum) { if !(n && k) return accum; if (k > rand() % n) return k_bit_helper(n - 1, k - 1, bit + bit, accum + bit); else return k_bit_helper(n - 1, k, bit + bit, accum); } unsigned long random_k_bits(int k) { return k_bit_helper(64, k, 1, 0); } 

The cost of generating the above will be dominated by the cost of generating random numbers (although in other solutions as well). You can optimize this a bit if you have a good prng by batch processing: for example, since you know that random numbers will be in steadily decreasing ranges, you can get random numbers for n through n-3 , getting a random number in the range 0..(n * (n - 1) * (n - 2) * (n - 3)) , and then extracting individual random numbers:

 r = randint(0, n * (n - 1) * (n - 2) * (n - 3) - 1); rn = r % n; r /= n rn1 = r % (n - 1); r /= (n - 1); rn2 = r % (n - 2); r /= (n - 2); rn3 = r % (n - 3); r /= (n - 3); 

The maximum value of n presumably 64 or 2 ^6; therefore, the maximum value of the above product is, of course, less than 2 ²⁴ . Indeed, if you used 64-bit prng, you could extract as many as 10 random numbers from it. However, do not do this unless you know that the prng that you use produces independently random bits.

Answer 6

I have another suggestion based on the enumeration: choose a random number i between 1 and n, choose k and generate the i-th combination. For example, for n = 6, k = 3 20 combinations:

 000111 001011 010011 100011 001101 010101 100101 011001 101001 110001 001110 010110 100110 011010 101010 110010 011100 101100 110100 111000 

Let's say we randomly choose the combination number 7. First we check whether it has 1 in the last position: it has, because there are the first 10 (5 select 2) combinations. Then we recursively check the remaining positions. Here is the C ++ code:

 word ithCombination(int n, int k, word i) { // i is zero-based word x = 0; word b = 1; while (k) { word c = binCoeff[n - 1][k - 1]; if (i < c) { x |= b; --k; } else { i -= c; } --n; b <<= 1; } return x; } word randomKBits(int k) { word i = randomRange(0, binCoeff[BITS_PER_WORD][k] - 1); return ithCombination(BITS_PER_WORD, k, i); } 

To be fast, we use pre-computed binomial coefficients in binCoeff . The randomRange function returns a random integer between two boundaries (inclusive).

I did some timings ( source ). With the default random number generator C ++ 11, most of the time is spent generating random numbers. Then this solution is the fastest because it uses an absolute minimum number of random bits. If I use a fast random number generator, then mic006 is the fastest. If it is known that k is very small, it is best to just set the bit until k are set.