Changes

Based on ideas of [[Walter Faxon]] and [[BitScan#DeBruijnMultiplation|De Bruijn Multiplication]], Matt came up with a [[BitScan#MattTaylorsFoldingtrick|genius folding trick]] as a quintessence <ref>[httphttps://groups.google.com/groupd/msg/comp.lang.asm.x86/browse_frm3pVGzQGb1ys/threadfPpKBKNi848J Bit magic] by [[Matt Taylor]], [https:/de9546cd019bd72b/f46209f47d2a7ddb?lnk=gst&q=Matt+Taylor+magicgroups.google.com/forum/#f46209f47d2a7ddb !forum/comp.lang.asm.x86 comp.lang.asm.x86], June 26, 2003</ref> <ref>[https://groups.google.com/d/msg/comp.lang.asm.x86/3pVGzQGb1ys/230qffQJYvQJ Re: Bit magic] by [[Matt Taylor]], [httphttps://groups.google.com/groupforum/#!forum/comp.lang.asm.x86/topics comp.lang.asm.x86], June 2629, 2003</ref>: For 64-bits, I do things a little differently simply because a 64-bit multiply is slow. I start out with x ^= (x - 1) just like normal which generates a key equal to 2^n - 1 (where n is the index of the LSB, 1 is index 0). Now fold the 64-bit key into 32-bits by xoring the high 32-bits with the low 32-bits. {| class="wikitable"|-! ls1b ! bb ^ (bb-1) ! folded |-| style="text-align:center;" | 63 | <code>0xffffffffffffffff</code> | <code>0x00000000</code> |-| style="text-align:center;" | 62 | <code>0x7fffffffffffffff</code> | <code>0x80000000</code> |-| style="text-align:center;" | 59 | <code>0x0fffffffffffffff</code> | <code>0xf0000000</code> |-| style="text-align:center;" | 32 | <code>0x00000001ffffffff</code> | <code>0xfffffffe</code> |-| style="text-align:center;" | 31 | <code>0x00000000ffffffff</code> | <code>0xffffffff</code> |-| style="text-align:center;" | 30 | <code>0x000000007fffffff</code> | <code>0x7fffffff</code> |-| style="text-align:center;" | 0 | <code>0x0000000000000001</code> | <code>0x00000001</code> |} 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 [[Hash Table#MinimalPerfectHashing|minimal perfect hashing]]: 

* [httphttps://groups.google.com/groupd/msg/comp.lang.asm.x86/3pVGzQGb1ys/fPpKBKNi848J Bit magic] by [[Matt Taylor]], [https://groups.google.com/forum/#!forum/comp.lang.asm.x86 comp.lang.asm.x86], June 26, 2003: [https://groups.google.com/browse_frmd/threadmsg/de9546cd019bd72b comp.lang.asm.x86/3pVGzQGb1ys/230qffQJYvQJ Re: Bit magic] by [[Matt Taylor]], [httphttps://groups.google.com/groupforum/#!forum/comp.lang.asm.x86/topics comp.lang.asm.x86], June 2629, 2003* [httphttps://groups.google.com/groupd/msg/comp.lang.asm.x86/msgGe1Uzd0WckM/26c662942c961ecd zR6WLJRixiYJ Re: Static memory allocation] by [[Matt Taylor]], [httphttps://groups.google.com/groupforum/#!forum/comp.lang.asm.x86/topics comp.lang.asm.x86], July 03, 2004