Author: Tijs van Dam
Date: 03:18:18 02/04/00
Go up one level in this thread
On February 03, 2000 at 17:47:04, Andreas G. Nowatzyk wrote:
>On alpha's the fastest way to count 1s in a 64 bit word is:
>
>unsigned CountOnes(unsigned long t)
>{
> unsigned long x, y;
>
> y = (t >> 1) & 0x7777777777777777;
> x = (y >> 1) & 0x7777777777777777;
> x = t - y - x - ((x >> 1) & 0x7777777777777777);
> return ((x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f) % 255;
>}
>
>if you are sure that there will never be more than 62 ones, there
>is a simple version of this:
>
>unsigned Ones(unsigned long x) /* HACKMEM 169 */
>{
> unsigned long y;
>
> y = (x >> 1) & 01333333333333333333333;
> y = x - y - ((y >> 1) & 01333333333333333333333);
> y = (y + (y >> 3)) & 0707070707070707070707;
> return y % 63;
>}
>
>(the original idea for this code originates from antic mainframe software)
That may be on alpha's (don't they have a cpu instruction for this), but for us,
poor people with 32-bits PC's, that is a lot of 64-bits instructions (especially
the shifts). The bitboards that you want to count (most in eval function)
usually have only a few bits in it, making the other routine faster.
Tijs
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.