Author: Manuel J. Petit de Gabriel
Date: 23:09:38 06/26/01
Go up one level in this thread
On June 26, 2001 at 08:48:19, Uri Blass wrote:
>This question is important for my move generator
>
>dirnow is a 16 bit non negative integer and I want to translate it to an array
>that include the place of it's digit.
>example:
>Suppose dirnow=131=2^7+2^1+2^0
>I want to get from dirnow the following information:
> directionsq[0]=7
> directionsq[1]=1
> directionsq[2]=0
>
>In most of the cases dirnow is a number with a lot of 0's and only few 1's.
>
>How to do it in the fastest way?
If the number of bits set is small you can try something similar to
the code below. For the example you gave (131) it does 100,000,000
computations in 6 seconds (celeron 466). For dirnow=1 it does the
same amount of iterations in 2.5 seconds... i don't know if this is
fast enough or you were looking for something faster. Find_bits()
fills the directionsq[] vector and returns the number of entries.
The speed only depends on the number of bits set to 1 and not in
their position.
manuel,
[freston@trillian /tmp/bits] ls
bits.c
[freston@trillian /tmp/bits] cat bits.c
unsigned log_tab[16]=
{
0xff,
0,
1, 0xff,
2, 0xff, 0xff, 0xff,
3, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff
};
inline
unsigned
log2(unsigned n)
{
unsigned ret;
ret= 0;
if(n> 0xff) {
n>>= 8;
ret+= 8;
}
if(n> 0x0f) {
n>>= 4;
ret+= 4;
}
ret+= log_tab[n];
return ret;
}
unsigned
find_bits(unsigned n, unsigned *tab)
{
unsigned ret;
unsigned bit;
unsigned log;
ret= 0;
while(n) {
bit= n&~(n-1);
n^= bit;
log= log2(bit);
tab[ret]= log;
ret++;
}
return ret;
}
main(int arc, char **argv)
{
unsigned i;
unsigned b[16];
unsigned parm= atoi(argv[1]);
for(i= 0; i< 100000000; i++) {
find_bits(parm, b);
}
return 0;
}
[freston@trillian /tmp/bits] make CFLAGS="-O3" bits
cc -O3 bits.c -o bits
[freston@trillian /tmp/bits] ./bits 1
[freston@trillian /tmp/bits] time ./bits 1
real 0m2.442s
user 0m2.400s
sys 0m0.001s
[freston@trillian /tmp/bits] time ./bits 131
real 0m5.924s
user 0m5.776s
sys 0m0.009s
[freston@trillian /tmp/bits] time ./bits 255
real 0m17.679s
user 0m17.385s
sys 0m0.009s
[freston@trillian /tmp/bits]
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.