Author: Ricardo Gibert
Date: 17:00:09 01/22/03
Go up one level in this thread
On January 22, 2003 at 08:28:11, Matt Taylor wrote: >I'm exploring the last couple possibilities in those bitscan routines. What I >have decided is that I will do bit = (bb & -bb) - 1 to get a mask that looks >like this: > >bit index mask (byte) >----------------------- > 1 0 00000000 > 2 1 00000001 > 4 2 00000011 > 8 3 00000111 > 16 4 00001111 > 32 5 00011111 > 64 6 00111111 >128 7 01111111 > >(Extrapolate for 32-bits; I'm lazy!) > >Now, this is convenient for me because x86 will record the last bit shifted out >into the carry flag. Furthermore, I can accomplish the index = (index << 1) | >((bit & mask) != 0) with a simple add with carry. That's pretty ideal for C -- 2 >instructions for 2 lines of code. Also, in the process, it modifies mask in a >potentially valuable way. > >All I need to make this a clever and slick way to eat bits. After the first >iteration, the masks for the second half of the table should be identical to the >masks in the first half. In other words, if the index >= 4, shift left 4, else >no-op. (A cmovz will sort've do it.) > >Alternatively, I can use subtraction to mess with the numbers and use the carry. > >Any suggestion would be welcome at any level of thought; higher-level concepts >may help me make a connection that I did not formerly see. Also, even more >complex expressions can sometimes be reduced very nicely. > >-Matt http://citeseer.nj.nec.com/cache/papers/cs/3312/ftp:zSzzSztheory.lcs.mit.eduzSzpubzSzcilkzSzdebruijn.pdf/leiserson98using.pdf
This page took 0.01 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.