Author: Robert Hyatt
Date: 19:39:37 04/19/00
Go up one level in this thread
On April 19, 2000 at 22:10:19, Flemming Rodler wrote: >Dear all, > > >Thanks for all the post I got to my thread "Bit counting below". For the problem >of counting the number of bits in a 64 bit variable I implemented the 3 schemes >suggested in the answers plus another scheme that I found on the web. Here are >my findings. > >Test computer: AMD K6-II 350 Mhz. > >Test: I timed how long each scheme took by calling them 2^20 and 4*2^20 times. > This was done for different number bits set to one. > >The different schemes are listed at the end of this post as Method 1,.. > >Result: for 2^20 repeatition. > > #bits on: 1 2 3 4 5 6 7 8 > ---------------------------------------------------------------------- > time in sec. Method 1: 0.07 0.10 0.12 0.15 0.17 0.19 0.22 0.24 > > Method 2: 0.15 regardless of #bits > Method 3: 0.20 > Method 4: 0.20 > > >Result: for 4*2^20 repeatition. > > #bits on: 1 2 3 4 5 6 7 8 > ---------------------------------------------------------------------- > time in sec. Method 1: 0.30 0.40 0.49 0.59 0.69 0.78 0.87 0.98 > > Method 2: 0.59 regardless of #bits > Method 3: 0.77 > Method 4: 0.77 > > >So we see that 4 bits is the break-even point for Method 1 and Method 2. >I do not know if it has any practical influence which methods you use in a chess >program but I might try it out with Crafty which I believe uses method 1 on a >PC. It would be interesting to change it to method 2 and see if there is a >significant change in the number of nodes searched per second. If so then it >might be good to use different versions when counting pawns and f.ex. queens. > Not worth testing. I did this exhaustively when I chose the bit counting code. I don't count things with several bits set very often... by far most of the counts are < 4, with the majority == 0... I don't count pawns using the bitmap, this is computed incrementally as part of the material signature... > >I hope you will find the info useful and if you have any ideas of how to make >them even faster please let me know so I can update the test results. > >Best regards >Flemming > > >Here are the 4 used methods. They were all compiled with gcc and -O3 turned onI >do not who to give credit for the various methods. Sorry for that. The first two >methods I have from the previous thread of posts. The third method I have from >the DarkThought webpages and the fourth method I got from the link supplied in >the previous posts. > > > >Method 1: >int bitcount1(register unsigned64 b) { > > register int c=0; > > for(;b;c++,b &= b-1); > > return c; >} > > >Method 2: >static char nbits[256] = >{ > 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, > 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, > 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, > 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, > 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, > 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, > 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, > 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, > 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, > 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, > 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, > 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, > 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, > 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, > 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, > 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, >}; > >int bitcount2(unsigned64 b) >{ > register unsigned long *n = (unsigned long *) &b; > return > nbits[(unsigned char) n[0]] + > nbits[(unsigned char) (n[0] >> 8)] + > nbits[(unsigned char) (n[0] >> 16)] + > nbits[(unsigned char) (n[0] >> 24)] + > nbits[(unsigned char) n[1]] + > nbits[(unsigned char) (n[1] >> 8)] + > nbits[(unsigned char) (n[1] >> 16)] + > nbits[(unsigned char) (n[1] >> 24)]; >} > > >Method 3: I added the register, but it not make any difference > >int bitcount3(register unsigned64 b) { > register unsigned32 n; > register const unsigned64 a = b - ((b >> 1) & m1); > register const unsigned64 c = (a & m2) + ((a >> 2) & m2); > n = ((unsigned32) c) + ((unsigned32) (c >> 32)); > n = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F); > n = (n & 0xFFFF) + (n >> 16); > n = (n & 0xFF) + (n >> 8); > return n; >} > > >Method 4: >int bitcount4(register unsigned64 b) >{ > register unsigned long i1,i2; > > i1 = ((b & 0xAAAAAAAAL) >> 1) + (b & 0x55555555L); > i1 = ((i1 & 0xCCCCCCCCL) >> 2) + (i1 & 0x33333333L); > i1 = ((i1 & 0xF0F0F0F0L) >> 4) + (i1 & 0x0F0F0F0FL); > i1 = ((i1 & 0xFF00FF00L) >> 8) + (i1 & 0x00FF00FFL); > i1 = ((i1 & 0xFFFF0000L) >> 16) + (i1 & 0x0000FFFFL); > > i2 = (((b>>32) & 0xAAAAAAAAL) >> 1) + ((b>>32) & 0x55555555L); > i2 = ((i2 & 0xCCCCCCCCL) >> 2) + (i2 & 0x33333333L); > i2 = ((i2 & 0xF0F0F0F0L) >> 4) + (i2 & 0x0F0F0F0FL); > i2 = ((i2 & 0xFF00FF00L) >> 8) + (i2 & 0x00FF00FFL); > i2 = ((i2 & 0xFFFF0000L) >> 16) + (i2 & 0x0000FFFFL); > > return (int)(i1+i2); >}
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.