Changes

[[FILE:EschersEye.jpg|border|right|thumb|187px|link=http://www.mcescher.com/Gallery/back-bmp/LW344.jpg|[[Arts#:Category:M. C. Escher|M. C. Escher]] - Eye, 1946 <ref>[http://www.mcescher.com/Gallery/gallery-back.htm Picture gallery "Back in Holland 1941 - 1954"] from [http://www.mcescher.com/ The Official M.C. Escher Website]</ref> ]]

Bitscan forward is identical with a '''Trailing Zero Count''' for none empty sets, possibly available as machine instruction on some architectures, for instance the [[x86-64]] bit-manipulation expansion set [[BMI1]], with some difficulties to use the [[BMI1#TZCNT|_tzcnt_u64]] intrisic with [https://en.wikipedia.org/wiki/Microsoft_Visual_Studio Visual Studio] <ref>[http://www.talkchess.com/forum3/viewtopic.php?f=7&t=74989 Looking for intrinsic "least significant bit" on Visual Studio] by [[Oliver Brausch]], [[CCC]], September 03, 2020</ref>.

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:

A branchless and little bit obfuscated version of the devide and conquer bitScanReverse with in-register-lookup <ref>[https://www.stmintz.com/ccc/index.php?id=472455 just another reverse bitscan] by [[Gerd Isenberg]], [[CCC]], December 22, 2005</ref> - as tribute to [[Videos#FrankZappa:Category:Frank Zappa|Frank Zappa]] with identifiers from [https://en.wikipedia.org/wiki/Freak_Out! Freak Out!] (1966), [https://en.wikipedia.org/wiki/Hot_Rats Hot Rats] (1969), [https://en.wikipedia.org/wiki/Waka/Jawaka Waka/Jawaka] (1972), [https://en.wikipedia.org/wiki/Sofa_%28Frank_Zappa_song%29 Sofa] (1975), [https://en.wikipedia.org/wiki/One_Size_Fits_All_%28Frank_Zappa_album%29 One Size Fits All] (1975), [https://en.wikipedia.org/wiki/Sheik_Yerbouti Sheik Yerbouti] (1979), and [https://en.wikipedia.org/wiki/Jazz_from_Hell Jazz from Hell] (1986):

While the [[BitScan#FrankZappa|tribute]] to [[Videos#FrankZappa:Category:Frank Zappa|Frank Zappa]] is quite 32-bit friendly <ref>[https://www.stmintz.com/ccc/index.php?id=472762 final version - homage to FZ] by [[Gerd Isenberg]], [[CCC]], December 23, 2005</ref>, [[Kim Walisch]] suggested to use the [[Parallel Prefix Algorithms|parallel prefix fill]] for a [[General Setwise Operations#TheMostSignificantOneBitMS1B|MS1B]] separation with the same [[De Bruijn Sequence|De Bruijn]] multiplication and lookup as in his [[BitScan#KimWalisch|bitScanForward]] routine with [[General Setwise Operations#LS1BSeparation|separated LS1B]], with less instructions in 64-bit mode. A log base 2 method was already devised by Eric Cole on January 8, 2006, and shaved off rounded up to one less than the next power of 2 by Mark Dickinson <ref>[https://ep2012.europython.eu/conference/p/mark-dickinson EuroPython 2012: Florence, July 2–8 | Mark Dickinson]</ref> on December 10, 2009, as published in Sean Eron Anderson's ''Bit Twiddling Hacks'' for 32-bit integers <ref>[http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn Find the log base 2 of an N-bit integer in O(lg(N)) operations with multiply and lookup] from [http://graphics.stanford.edu/%7Eseander/bithacks.html Bit Twiddling Hacks] by [http://graphics.stanford.edu/%7Eseander/ Sean Eron Anderson]</ref>.

While [[Bitboard Serialization|traversing sets]], one may combine bitscanning with reset found bit. That implies passing the bitboard per reference or pointer, and tends to confuse compilers to keep all inside registers inside a typical serialization loop <ref>[https://www.stmintz.com/ccc/index.php?id=283655 Bitscan] by [[Matt Taylor]], [[CCC]], February 11, 2003</ref> <ref>[http://www.talkchess.com/forum3/viewtopic.php?f=7&t=70202 CPW bitscan with reset could someone explain this line?] by [[Mahmoud Uthman]], [[CCC]], March 14, 2019</ref> .

[https://en.wikipedia.org/wiki/Haswell_%28microarchitecture%29 Haswell] <ref>[http://users.atw.hu/instlatx64/GenuineIntel00306C3_Haswell_InstLatX64.txt Haswell Instructions Latency]</ref>

| style="text-align:center;" | [[BMI1#LZCNT|TZCNT]]

* [https://www.stmintz.com/ccc/index.php?id=20057 Question to Bob: Crafty , Alpha and FindBit()] by [[Guido Schimmels]], [[CCC]], June 05, 1998» [[Crafty]], [[DEC Alpha]]

* [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: [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ürssnerBürßner]], [[CCC]], December 30, 2003 » [[De Bruijn Sequence Generator]]

* [http://www.talkchess.com/forum/viewtopic.php?t=54798 Stockfish 32-bit and hardware instructions on MSVC++] by [[Syed Fahad]], [[CCC]], December 30, 2014 » [[Stockfish]], [[BitScan]], [[Population Count]]

* [[Videos#FrankZappa:Category:Frank Zappa|Frank Zappa]] & [https://en.wikipedia.org/wiki/The_Mothers_of_Invention the Mothers] - [https://en.wikipedia.org/wiki/King_Kong King Kong] BBC Studio Recording 1968, [https://en.wikipedia.org/wiki/YouTube YouTube] Video