Need a way to pick a common bit in two bitmasks at random

Question

Imagine two bitmasks, I'll just use 8 bits for simplicity:

01101010
10111011

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).

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 & them together to initially check if there's any common bits at all.

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!

Mike

Answer 1

If you are willing to have an O(lg n) solution, at the cost of a possibly nonuniform probability, recursively half split, i.e. and with the top half of the bits set and the bottom half set. If both are nonzero then chose one randomly, else choose the nonzero one. Then half split what remains, etc. This will take 10 comparisons for a 32 bit number, maybe not as few as you would like, but better than 32.

You can save a few ands by choosing to and with the high half or low half at random, and if there are no hits taking the other half, and if there are hits taking the half tested.

The random number only needs to be generated once, as you are only using one bit at each test, just shift the used bit out when you are done with it.

If you have lots of bits, this will be more efficient. I do not see how you can get this down to O(1) though.

For example, if you have a 32 bit number first and the anded combination with either 0xffff0000 or 0x0000ffff if the result is nonzero (say you anded with 0xffff0000) conitinue on with 0xff000000 of 0x00ff0000, and so on till you get to one bit. This ends up being a lot of tedious code. 32 bits takes 5 layers of code.

Answer 2

Do you want a uniform random distribution? If so, I don't see any good way around counting the bits and then selecting one at random, or selecting random bits until you hit one that is set.

If you don't care about uniform, you can select a set bit out of a word randomly with:

unsigned int pick_random(unsigned int w, int size) {
    int bitpos = rng() % size;
    unsigned int mask = ~((1U << bitpos) - 1);
    if (mask & w)
        w &= mask;
    return w - (w & (w-1));
}

where rng() is your random number generator, w is the word you want to pick from, and size is the relevant size of the word in bits (which may be the machine wordsize, or may be less as long as you don't set the upper bits of the word. Then, for your example, you use pick_random(0x6a & 0xbb, 8) or whatever values you like.

Answer 3

This function uniformly randomly selects one bit which is high in both masks. If there are no possible bits to pick, zero is returned instead. The running time is O(n), where n is the number of high bits in the anded masks. So if you have a low number of high bits in your masks, this function could be faster even though the worst case is O(n) which happens when all the bits are high. The implementation in C is as follows:

unsigned int randomMasksBit(unsigned a, unsigned b){
    unsigned int i = a & b; // Calculate the bits which are high in both masks.
    unsigned int count = 0
    unsigned int randomBit = 0;
    while (i){ // Loop through all high bits.
        count++;
        // Randomly pick one bit from the bit stream uniformly, by selecting 
        // a random floating point number between 0 and 1 and checking if it 
        // is less then the probability needed for random selection.
        if ((rand() / (double)RAND_MAX) < (1 / (double)count)) randomBit = i & -i;
        i &= i - 1; // Move on to the next high bit.
    }
    return randomBit;
}

Answer 4

O(1) with uniform distribution (or as uniform as random generator offers) can be done, depending on whether you count certain mathematical operation as O(1). As a rule we would, though in the case of bit-tweaking one might make a case that they are not.

The trick is that while it's easy enough to get the lowest set bit and to get the highest set bit, in order to have uniform distribution we need to randomly pick a partitioning point, and then randomly pick whether we'll go for the highest bit below it or the lowest bit above (trying the other approach if that returns zero).

I've broken this down a bit more than might be usual to allow the steps to be more easily followed. The only question on constant timing I can see is whether Math.Pow and Math.Log should be considered O(1).

Hence:

public static uint FindRandomSharedBit(uint x, uint y)
{//and two nums together, to find shared bits.
  return FindRandomBit(x & y);
}
public static uint FindRandomBit(uint val)
{//if there's none, we can escape out quickly.
  if(val == 0)
    return 0;
  Random rnd = new Random();
  //pick a partition point. Note that Random.Next(1, 32) is in range 1 to 31
  int maskPoint = rnd.Next(1, 32);
  //pick which to try first.
  bool tryLowFirst = rnd.Next(0, 2) == 1;
  // will turn off all bits above our partition point.
  uint lowerMask = Convert.ToUInt32(Math.Pow(2, maskPoint) - 1);
  //will turn off all bits below our partition point
  uint higherMask = ~lowerMask;
  if(tryLowFirst)
  {
    uint lowRes = FindLowestBit(val & higherMask);
    return lowRes != 0 ? lowRes : FindHighestBit(val & lowerMask);
  }
  uint hiRes = FindHighestBit(val & lowerMask);
  return hiRes != 0 ? hiRes : FindLowestBit(val & higherMask);
}
public static uint FindLowestBit(uint masked)
{                                  //e.g  00100100
  uint minusOne = masked - 1;      //e.g. 00100011
  uint xord = masked ^ minusOne;   //e.g. 00000111
    uint plusOne = xord + 1;       //e.g. 00001000
    return plusOne >> 1;           //e.g. 00000100
}
public static uint FindHighestBit(uint masked)
{
    double db = masked;
    return (uint)Math.Pow(2, Math.Floor(Math.Log(masked, 2)));
}

Answer 5

I believe that, if you want uniform, then the answer will have to be Theta(n) in terms of the number of bits, if it has to work for all possible combinations.

The following C++ snippet (stolen) should be able to check if any given num is a power of 2.

    if (!var || (var & (var - 1))) {
        printf("%u is not power of 2\n", var);
    }
    else {
        printf("%u is power of 2\n", var);
    }

Answer 6

If you have few enough bits to worry about, you can get O(1) using a lookup table:

var lookup8bits = new int[256][] = {
    new [] {},
    new [] {0},
    new [] {1},
    new [] {0, 1},
    ...
    new [] {0, 1, 2, 3, 4, 5, 6, 7}
};

Failing that, you can find the least significant bit of a number x with (x & -x), assuming 2s complement. For example, if x = 46 = 101110b, then -x = 111...111010010b, hence x & -x = 10. You can use this technique to enumerate the set bits of x in O(n) time, where n is the number of set bits in x.

Note that computing a pseudo random number is going to take you a lot longer than enumerating the set bits in x!