Computer Chess Club Archives

Search

Messages

Subject: Re: How can you get the number of a bit which is set in a bitboard ?

Author: Andrew Slough

Date: 11:03:51 08/20/99

Go up one level in this thread

I was shown a nice algorithm for this a while ago which happens to work really
well on ARM processors because the multiply gets split into shifts and adds.
This is for 32-bit values, but you can use it for bitboards by splitting it into
two:

static const unsigned char table[64] = {
                   0x20, 0x00, 0x01, 0x0c,  0x02, 0x06, 0xff, 0x0d,
                   0x03, 0xff, 0x07, 0xff,  0xff, 0xff, 0xff, 0x0e,
                   0x0a, 0x04, 0xff, 0xff,  0x08, 0xff, 0xff, 0x19,
                   0xff, 0xff, 0xff, 0xff,  0xff, 0x15, 0x1b, 0x0f,
                   0x1f, 0x0b, 0x05, 0xff,  0xff, 0xff, 0xff, 0xff,
                   0x09, 0xff, 0xff, 0x18,  0xff, 0xff, 0x14, 0x1a,
                   0x1e, 0xff, 0xff, 0xff,  0x17, 0x17, 0xff, 0x13,
                   0x1d, 0xff, 0x16, 0x12,  0x1c, 0x11, 0x10, 0xff
};

int ffs(unsigned int w)
{
                   return table[((w&(-w)) * 0x0450fbaf) >> 26];
}

Andy

• Re: How can you get the number of a bit which is set in a bitboard ? Andrew Slough 11:12:46 08/20/99

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.