Need a way to pick a common bit in two bitmasks at random <p>Imagine two bitmasks, I'll just use 8 bits for simplicity:</p> <pre><code>01101010 10111011 </code></pre> <p>The 2nd, 4th, and 6th bits are both 1. I want to pick one of those common "on" bits at random. But I want to do this in O(1).</p> <p>The only way I've found to do this so far is pick a random "on" bit in one, then check the other to see if it's also on, then repeat until I find a match. This is still O(n), and in my case the majority of the bits are off in both masks. I do of course &amp; them together to initially check if there's any common bits at all.</p> <p>Is there a way to do this? If so, I can increase the speed of my function by around 6%. I'm using C# if that matters. Thanks!</p> <p>Mike</p>