Changes

Jump to: navigation, search

BitScan

48 bytes added, 13:56, 29 June 2018
no edit summary
'''[[Main Page|Home]] * [[Board Representation]] * [[Bitboards]] * BitScan'''
[[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''',<br/>
<span id="FrankZappa"></span>
==Tribute to Frank Zappa==
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):
<pre>
typedef unsigned __int64 OneSizeFits;
<span id="FillDeBruijn"></span>
==De Bruijn Multiplication==
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>.
<pre>
const int index64[64] = {
* [http://caladan.nanosoft.ca/c4/software/bitsort.php An Efficient Bit-Reversal Sorting Algorithm for the Fast Fourier Transform] by [http://caladan.nanosoft.ca/index.php Jennifer Elaan], January 16, 2005
* [http://www.freepatentsonline.com/6172623.html Efficient bit scan mechanism - United States Patent 6172623] from [http://www.freepatentsonline.com/ FreePatentsOnline.com]
* [[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
: {{#evu:https://www.youtube.com/watch?v=kk8mPKROUS4|alignment=left|valignment=top}}
'''[[Bitboards|Up one Level]]'''
[[Category:M. C. Escher]]
[[Category:Frank Zappa]]

Navigation menu