Page 1 of 1
Bit position hack
Posted: Sun Sep 01, 2013 1:45 am
by 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
Re: Bit position hack
Posted: Sun Sep 01, 2013 5:54 am
by BB+
Maybe: rotate a random amount (from 0 to 63), then take the lowest bit, then undo the rotation.
Re: Bit position hack
Posted: Sun Sep 01, 2013 3:04 pm
by 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];
}
Re: Bit position hack
Posted: Sun Sep 01, 2013 4:08 pm
by 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.
Re: Bit position hack
Posted: Sun Sep 01, 2013 10:02 pm
by syzygy
nak3c wrote: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.
Re: Bit position hack
Posted: Sun Sep 01, 2013 10:20 pm
by 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.
Re: Bit position hack
Posted: Mon Sep 02, 2013 12:48 am
by 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.