Matt Taylor
On this page
Matt Taylor was involved in forum discussions on low level optimization and x86 assembly language issues. Beside other things Matt was busy to optimize a minimal perfect hashing scheme for bitscan purposes.
Based on ideas of Walter Faxon and De Bruijn Multiplication, Matt came up with a genius folding trick as a quintessence [1] [2]:
| ls1b | bb ^ (bb-1) | folded
63 | ||
0xffffffffffffffff | 0x00000000 | |
62 | ||
0x7fffffffffffffff | 0x80000000 | |
59 | ||
0x0fffffffffffffff | 0xf0000000 | |
32 | ||
0x00000001ffffffff | 0xfffffffe | |
31 | ||
0x00000000ffffffff | 0xffffffff | |
30 | ||
0x000000007fffffff | 0x7fffffff | |
0 | ||
0x0000000000000001 | 0x00000001 |
Even if this folded “LS1B” contains multiple consecutive one-bits, the multiplication is De Bruijn like. There are only two magic 32-bit constants with the combined property of 32- and 64-bit De Bruijn Sequences to apply this minimal perfect hashing:
Forum Posts
- Bitscan Conclusions by Matt Taylor, CCC, January 05, 2003
- Cleverness, Please! by Matt Taylor, CCC, January 22, 2003
- Bitscan by Matt Taylor, CCC, February 11, 2003
- Bit magic by Matt Taylor, comp.lang.asm.x86, June 26, 2003
Re: Bit magic by Matt Taylor, comp.lang.asm.x86, June 29, 2003
- Re: Static memory allocation by Matt Taylor, comp.lang.asm.x86, July 03, 2004
References
- ↑ Bit magic by Matt Taylor, comp.lang.asm.x86, June 26, 2003
- ↑ Re: Bit magic by Matt Taylor, comp.lang.asm.x86, June 29, 2003