Algorithms for selecting a number uniformly randomly from a subset of integers

If the associated bits are irregular, i.e. cannot be deduced from the value of i by a simple formula, then it is just impossible to locate the r-th '0' bit without enumerating those that precede, unless preprocessing is allowed.

A good solution is to precompute a table that will store the indexes of the '0' bit entries contiguously, and lookup this table for the r-th entry. (Instead of an index table, you can as well fill another array with the elements from the subset only.)

Indexing a packed bit array is not such a big deal. Assuming 64 bits long ints, the bit at index i is found by the expression

(PackedBits[i >> 6] >> (i & 63)) & 1 

(The 6 because 64 == (1 << 6).)

In case you really want to find the r-th '0' sequentially, you can speed-up the search a little (x 64) by precomputing the number of '0's in every long int so that you can skip 64 entries in a single go.

And if you really really don't want to precompute anything, you can still speed-up the search by processing the bits 8 by 8, using a static table that relates every byte value (among 256) to the number of '0' bits in it. (Or even 16 by 16 if you can afford using a table of 65536 numbers.)

You can speed this up by trading memory for speed.

T must be an array, that stores in T[n] the number of integers in a[] that have bit n cleared, and this needs to be precomputed at some point. So, while you are calculating that, store the indices of all the integers that have a given bit cleared in another 2 dimensional array, indexed by the bit number and r.

In C for example:

#define BITS (64) #define N (100) long int a[N]; int T[BITS]; int index[BITS][N]; void init() { int i, j; // clear T: for(j = 0; j < BITS; j++) T[j] = 0; // compute T and the indices for each: for(i = 0; i < N; i++) { for(j = 0; j < BITS; j++) { if((a[i] & (1 << j)) == 0) { // increment T and store the index index[j][T[j]++] = i; } } } } 

Then you can find your random number like this:

long number = N[index[bit][rand() % T[bit]]; 

You could make this more memory-efficient by using a less wasteful data structure that only stores as many indices for each bit as there are actual values in a[] that have the bit cleared.

If T is sufficiently large, the most efficient solution is going to be to randomly select an integer up to N and loop until the condition is met.