Home > Archive > Fortran > August 2005 > Re: finding rightmost zero bit
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Re: finding rightmost zero bit
|
|
| ttw@texasairnet.com 2005-08-30, 3:56 am |
| For a chess-playing program I found the following the fastest. First,
check if N>2**32 then check against the 2**16 and 3*2**16; continue
down to 8 bits. (Using a binary search this takes only 3 tests.) This
gives a partial answer. The previous answer is then completed by taking
the unknown byte and using a table lookup: 00000000=1, 000000001=1,
00000010=2,00000011=1, etc. A similar method was fastest for leading 1
bits.
| |
| glen herrmannsfeldt 2005-08-30, 3:56 am |
| ttw@texasairnet.com wrote:
> For a chess-playing program I found the following the fastest. First,
> check if N>2**32 then check against the 2**16 and 3*2**16; continue
> down to 8 bits. (Using a binary search this takes only 3 tests.) This
> gives a partial answer. The previous answer is then completed by taking
> the unknown byte and using a table lookup: 00000000=1, 000000001=1,
> 00000010=2,00000011=1, etc. A similar method was fastest for leading 1
> bits.
I thought about one like that, but it wasn't so easy to get the
bytes out of an integer in standard Fortran, and probably even
harder in F. Doing it with shifts takes enough more than I was
otherwise doing that I didn't try it. Though it depends much on
the cost of the conditional branch or conditional load, so I
can't really say. But yes, in general I prefer table lookups.
-- glen
|
|
|
|
|