Changes

Jump to: navigation, search

BitScan

285 bytes added, 16:29, 27 February 2019
no edit summary
<span id="MattTaylorsFoldingtrick"></span>
==Matt Taylor's Folding trick==
A 32-bit friendly implementation to find the the bit-index of [[General Setwise Operations#TheLeastSignificantOneBitLS1B|LS1B]] by [[Matt Taylor]] <ref>[httphttps://groups.google.com/groupd/msg/comp.lang.asm.x86/browse_frm3pVGzQGb1ys/fPpKBKNi848J Bit magic] by [[Matt Taylor]], [https://threadgroups.google.com/de9546cd019bd72bforum/f46209f47d2a7ddb?lnk=gst&q=Matt+Taylor+magic#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>. The [[General Setwise Operations#ExclusiveOr|xor]] with the ones' decrement, [[General Setwise Operations#LS1BSeparation|bb ^ (bb-1)]] contains all bits set including and below the [[General Setwise Operations#TheLeastSignificantOneBitLS1B|LS1B]]. The 32-bit xor-difference of both halves yields either the complement of the upper half, or the lower half otherwise. Some samples:
{| class="wikitable"
|-
* [https://www.stmintz.com/ccc/index.php?id=283655 Bitscan] by [[Matt Taylor]], [[CCC]], February 11, 2003
* [https://www.stmintz.com/ccc/index.php?id=291062 FirstOne for Linux] by [[Sune Fischer]], [[CCC]], March 29, 2003
* [httphttps://groups.google.com/groupd/msg/comp.lang.asm.x86/browse_frm3pVGzQGb1ys/fPpKBKNi848J Bit magic] by [[Matt Taylor]], [https://threadgroups.google.com/de9546cd019bd72bforum/f46209f47d2a7ddb?lnk=gst&q=Matt+Taylor+magic#f46209f47d2a7ddb !forum/comp.lang.asm.x86 comp.lang.asm.x86], June 26, 2003: [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
* [https://www.stmintz.com/ccc/index.php?id=339225 Re: De Bruijn Sequence Generator] by [[Dieter Bürßner]], [[CCC]], December 30, 2003 » [[De Bruijn Sequence Generator]]
* [https://www.stmintz.com/ccc/index.php?id=348097 Determining location of LSB/MSB] by [[Jan Renze Steenhuisen|Renze Steenhuisen]], [[CCC]], February 09, 2004

Navigation menu