Bit position hack

[nak3c]

Im looking for a bitposition hack that does the following quickly

suppose I have a bitfield 0b011010

Im looking for a quick function to return the position of one of the ones randomly ie

randomsetposition ( 0b011010 ) { // return 1, 3, or 4 randomly

theres got to be a better way than looping or guess and check, Thanks

[BB+]

Maybe: rotate a random amount (from 0 to 63), then take the lowest bit, then undo the rotation.

[geko]

typedef struct {
int n;
int r[8];
} node;

node x[256];

void init(){//once time

..
x[0b00000011].n=2;
x[0b00000011].r[0]=0;
x[0b00000011].r[1]=1;
..
x[0b00011010].n=3;
x[0b00011010].r[0]=1;
x[0b00011010].r[1]=3;
x[0b00011010].r[2]=4;
..
/fill all x entries
}

int randomsetposition ( 0b00011010 ) {
return x[0b00011010].r[random()%x[0b00011010].n];
}

[nak3c]

thanks Geko, thats a fast solution; unfortunatly I was hoping this function would work for 64bit numbers and it would require too much memory for tables that big. may look into the rotation idea.

[syzygy]

thanks Geko, thats a fast solution; unfortunatly I was hoping this function would work for 64bit numbers and it would require too much memory for tables that big. may look into the rotation idea.

The rotation idea will not give a uniform distribution. But whether that is important depends on what you need it for. Personally I don't see how this could be useful in a chess engine.

To get a uniform random distribution you could start with a popcount to determine the number N of 1s, then pick a random number 0 <= n < N, do "bits &= bits - 1" n times and then take the lowest 1 using a bitscan instruction.

[syzygy]

For Haswell cpus, the following should work:

Code: Select all

int pick_random_bit(uint64 bits)
{
  int n = __builtin_popcountll(bits);
  int r = some_random_generator() % n;
  uint64 b = 1ULL << r;
  bits = _pdep_u64(b, bits);
  return __builtin_ffsll(bits);
}

but whether that's faster remains to be seen.

Maybe something smarter is possible with pext/pdep.

[nak3c]

Thanks for the responses ill try them out. The "usefulness" stems from me wanting to try some stochastic monte carlo stuff even though it has not been shown to work well for chess.