Pick random bit from 32bit value in O(1) if possible

Question

I have a 32bit random value (say 631).

0...0000001001110111

Each of these bits is a flag. I would like to return a random flag from these bits in, if at all possible, O(1) operation. How would I select the bit position 0, 1, 2, 4, 5, 6 or 9 (or it's corresponding value 1, 2, 4, 16, 32, 64, 512) from the given value 631? Preferably with as least possible bias towards some bits.

Things I came up with:

1. • Shift value right random number of bits (max. 10 in this case)
   • See if LSB is set
     • If it is: got a bit position (last shifted number of bits); done
     • if not:
       • If resulting value == 0; start over
       • If resulting value != 0, go back to shifting random bits again

Above is not O(1) and possibly need multiple iterations if we happen to only 'hit' the 0 bits.

2. • Mask (and) with random value
   • Repeat until power of 2 is left or start over when value is 0.

Again, above is not O(1) unfortunately.

I'm pretty sure this must be possible with some bithisfting/masking/magic somehow...

---

Edit:

As CodeCaster suggested; this will give me all set bit values:

int myvalue = 631;
var matchingmasks = Enumerable.Range(0, 32)
                              .Select(i => 1 << i)
                              .Where(i => (myvalue & i) == i)
                              .ToArray();

From the resulting array I can pick a random element and I'll have found my 'random' bit (flag) from the given value. However, this still requires a (hidden, because Linq) for-loop, 'brute-forcing' each possible bit, memory allocations for the resulting array etc.

Answer 1

First off, I would suggest doing this the easy, straightforward, obvious way that you suggest in the question: make an array of values, choose an element at random. Yes this allocates memory and whatnot. Optimize for the code being readable and correct first; only when you have a demonstrated performance problem should you optimize it.

If you do want to optimize it down to bit twiddling, this page is my go-to resource: http://graphics.stanford.edu/~seander/bithacks.html

The algorithms you'll want here are:

• first, pick your favourite algorithm for determining the Hamming weight -- that is, "how many bits are on?" Call that number n.
• Now pick a random number r from 1 to n
• Now read the algorithm called "select the bit position with the given count". This takes your number r and gives you the bit position of the rth true bit starting from the high end. The code given on the page is for longs; it should be straightforward to modify it for ints.

I note that a key feature of many of these algorithms is that they are branchless. When you are trying to wring the last ounce of performance out of an algorithm, remember that every "if" kills performance. An "if" means that there is code in the cache that is NOT running, because you branched away from it, and therefore you are making a cache miss more likely. An "if" means there is an opportunity for the branch predictor to make the wrong choice. At the CLR level, every "if" means more basic blocks, which means more work for the jitter to do its flow analysis. And so on.

Answer 2

You can simply create the masks on beforehand, and select the masks that match the source value:

uint source = 631;
uint[] masks = Enumerable.Range(0, 32).Select(i => (uint)1 << i).ToArray();
uint[] matchingMask = masks.Where(m => (m & source) == m).ToArray();

Now matchingMask contains the values that make up your source value, in this case: 1, 2, 4, 16, 32, 64, 512.

Then from matchingMask you can select a random element.

If you want the bit position instead, you could use the indexing Select() overload like this:

var matchingMask = masks.Select((m, i) => new { Index = i, Mask = m}) 
                        .Where(m => (m.Mask & source) == m.Mask)
                        .ToArray();