25,161
edits
Changes
Created page with "'''Home * Programming * Bit-Twiddling''' '''Bit-twiddling''' is a family of techniques used in [https://en.wikipedia.org/wiki/Bit_manipulation manipulating]..."
'''[[Main Page|Home]] * [[Programming]] * Bit-Twiddling'''
'''Bit-twiddling''' is a family of techniques used in [https://en.wikipedia.org/wiki/Bit_manipulation manipulating] integers in a non-obvious manner in order to obtain a result either more quickly or with less code. Bit-twiddling is often associated with [[Bitboards|bitboards]], but there are both easy-to-read [[Bitboards|bitboard]] implementations and difficult-to-read implementations of other board representations.
=Bit-Twiddling related to Bitboards=
* [[BitScan]]
* [[Flipping Mirroring and Rotating]]
* [[Kogge-Stone Algorithm|Kogge-Stone]]
* [[General Setwise Operations#TheLeastSignificantOneBitLS1B|Obtaining and Clearing the Least Significant Bit (LS1B)]]
* [[Population Count]]
* [[Traversing Subsets of a Set]]
<span id="BitManipulation"></span>
=Bit-Manipulation=
* [[SSE4#ABM|ABM]]
* [[BMI1]]
* [[BMI2]]
* [[General Setwise Operations]]
* [[TBM]]
=Forum Posts=
* [http://talkchess.com/forum/viewtopic.php?t=29269 Bit twiddlement question: greater of two popcounts] by [[Zach Wegner]], [[CCC]], August 06, 2009
* [http://talkchess.com/forum/viewtopic.php?t=29333 Bit twiddling question, part 2: arbitrary bitscan order] by [[Zach Wegner]], [[CCC]], August 11, 2009
* [http://www.open-chess.org/viewtopic.php?f=5&t=2419 Bit position hack] by nak3c, [[Computer Chess Forums|OpenChess Forum]], September 01, 2013
=Important online resources=
Online Papers by [[Donald Knuth]]:
* [http://www-cs-faculty.stanford.edu/%7Eknuth/preprints.html Preprints of Recent Papers] including [https://en.wikipedia.org/wiki/Dancing_Links dancing links]
* [http://www-cs-faculty.stanford.edu/%7Eknuth/taocp.html The Art of Computer Programming]
: '''Vol 4''' as Pre-Fascicle PostScripts:
* [http://www-cs-faculty.stanford.edu/%7Eknuth/fasc0b.ps.gz Pre-Fascicle 0b (Boolean basics)]
* [http://www-cs-faculty.stanford.edu/%7Eknuth/fasc0c.ps.gz Pre-Fascicle 0c (Boolean evaluation)]
* [http://www-cs-faculty.stanford.edu/%7Eknuth/fasc1a.ps.gz Pre-Fascicle 1a (Bitwise tricks and techniques)]
Online [[Papers]] by [[Henry S. Warren, Jr.]]
* [[Henry S. Warren, Jr.#HackersDeligh|Hacker’s Delight]], [http://www.informit.com/store/product.aspx?isbn=0321842685 2nd Edition]
* [http://www.hackersdelight.org/basics1.pdf Sample section of Hacker's Delight, Chapter 2 Basics] (pdf)
* [http://www.hackersdelight.org/hdcode.htm C code for most of the programs that appear in HD]
=Other Bit-Twiddling resources=
* Michael Beeler, [[Bill Gosper]], [https://en.wikipedia.org/wiki/Richard_Schroeppel Rich Schroeppel] ('''1972'''). ''[http://home.pipeline.com/~hbaker1/hakmem/hakmem.html HAKMEM]'', Memo 239, Artificial Intelligence Laboratory, [[Massachusetts Institute of Technology]],
: Web-available by [http://home.pipeline.com/~hbaker1/ Henry Baker]
: [http://www.cl.cam.ac.uk/~am21/hakmemc.html HAKMEMC -- HAKMEM Programming hacks in C] by [http://www.cl.cam.ac.uk/~am21/ Alan Mycroft]
: [https://en.wikipedia.org/wiki/HAKMEM HAKMEM from Wikipedia]
* [http://www.jjj.de/fxt/fxtbook.pdf Matters Computational - ideas, algorithms, source code] (pdf) Ideas and Source Code by [[Mathematician#Arndt|Jörg Arndt]]
* [http://aggregate.org/MAGIC The Aggregate Magic Algorithms] by [[Hank Dietz]]
* [http://graphics.stanford.edu/%7Eseander/bithacks.html Bit Twiddling Hacks] by [http://graphics.stanford.edu/%7Eseander/ Sean Eron Anderson]
* [http://bits.stephan-brumme.com/ the bit twiddler] by [http://www.stephan-brumme.com/ Stephan Brumme]
* [http://programming.sirrida.de Programming pages] of [http://sourceforge.net/users/jasper_neumann/ Jasper Neumann]
* [https://github.com/keon/awesome-bits GitHub - keon/awesome-bits: A curated list of awesome bitwise operations and tricks]
* [http://www.onjava.com/pub/a/onjava/2005/02/02/bitsets.html Bitwise Optimization in Java: Bitfields, Bitboards, and Beyond] by [[Glen Pepicelli]], 2005, [https://en.wikipedia.org/wiki/O%27Reilly_Media O'Reilly's] [http://onjava.com/ OnJava.com] » [[Java]], [[Bitboards]]
* [https://github.com/golang/go/issues/18616 math/bits: an integer bit twiddling library · Issue #18616 · golang/go · GitHub] » [[Go (Programming Language)]]
=External Links=
* [https://en.wikipedia.org/wiki/Bit_twiddler Bit twiddler from Wikipedia]
* [https://en.wikipedia.org/wiki/Bit_manipulation Bit manipulation from Wikipedia]
* [http://mridulm.blogspot.com/2006/09/bit-twiddling.html bit twiddling ...] from [http://mridulm.blogspot.com/ Random thoughts] blog by [[Mridul Muralidharan]]
* [http://zimbry.blogspot.de/ Twiddling the Bits] by [[David Stafford]]
* [[Videos#NHOP|NHØP]] & [[Videos#TaniaMaria|Tania Maria]] - Baião improvisado, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=7zbY6URSZ-U|alignment=left|valignment=top}}
'''[[Programming|Up one Level]]'''
'''Bit-twiddling''' is a family of techniques used in [https://en.wikipedia.org/wiki/Bit_manipulation manipulating] integers in a non-obvious manner in order to obtain a result either more quickly or with less code. Bit-twiddling is often associated with [[Bitboards|bitboards]], but there are both easy-to-read [[Bitboards|bitboard]] implementations and difficult-to-read implementations of other board representations.
=Bit-Twiddling related to Bitboards=
* [[BitScan]]
* [[Flipping Mirroring and Rotating]]
* [[Kogge-Stone Algorithm|Kogge-Stone]]
* [[General Setwise Operations#TheLeastSignificantOneBitLS1B|Obtaining and Clearing the Least Significant Bit (LS1B)]]
* [[Population Count]]
* [[Traversing Subsets of a Set]]
<span id="BitManipulation"></span>
=Bit-Manipulation=
* [[SSE4#ABM|ABM]]
* [[BMI1]]
* [[BMI2]]
* [[General Setwise Operations]]
* [[TBM]]
=Forum Posts=
* [http://talkchess.com/forum/viewtopic.php?t=29269 Bit twiddlement question: greater of two popcounts] by [[Zach Wegner]], [[CCC]], August 06, 2009
* [http://talkchess.com/forum/viewtopic.php?t=29333 Bit twiddling question, part 2: arbitrary bitscan order] by [[Zach Wegner]], [[CCC]], August 11, 2009
* [http://www.open-chess.org/viewtopic.php?f=5&t=2419 Bit position hack] by nak3c, [[Computer Chess Forums|OpenChess Forum]], September 01, 2013
=Important online resources=
Online Papers by [[Donald Knuth]]:
* [http://www-cs-faculty.stanford.edu/%7Eknuth/preprints.html Preprints of Recent Papers] including [https://en.wikipedia.org/wiki/Dancing_Links dancing links]
* [http://www-cs-faculty.stanford.edu/%7Eknuth/taocp.html The Art of Computer Programming]
: '''Vol 4''' as Pre-Fascicle PostScripts:
* [http://www-cs-faculty.stanford.edu/%7Eknuth/fasc0b.ps.gz Pre-Fascicle 0b (Boolean basics)]
* [http://www-cs-faculty.stanford.edu/%7Eknuth/fasc0c.ps.gz Pre-Fascicle 0c (Boolean evaluation)]
* [http://www-cs-faculty.stanford.edu/%7Eknuth/fasc1a.ps.gz Pre-Fascicle 1a (Bitwise tricks and techniques)]
Online [[Papers]] by [[Henry S. Warren, Jr.]]
* [[Henry S. Warren, Jr.#HackersDeligh|Hacker’s Delight]], [http://www.informit.com/store/product.aspx?isbn=0321842685 2nd Edition]
* [http://www.hackersdelight.org/basics1.pdf Sample section of Hacker's Delight, Chapter 2 Basics] (pdf)
* [http://www.hackersdelight.org/hdcode.htm C code for most of the programs that appear in HD]
=Other Bit-Twiddling resources=
* Michael Beeler, [[Bill Gosper]], [https://en.wikipedia.org/wiki/Richard_Schroeppel Rich Schroeppel] ('''1972'''). ''[http://home.pipeline.com/~hbaker1/hakmem/hakmem.html HAKMEM]'', Memo 239, Artificial Intelligence Laboratory, [[Massachusetts Institute of Technology]],
: Web-available by [http://home.pipeline.com/~hbaker1/ Henry Baker]
: [http://www.cl.cam.ac.uk/~am21/hakmemc.html HAKMEMC -- HAKMEM Programming hacks in C] by [http://www.cl.cam.ac.uk/~am21/ Alan Mycroft]
: [https://en.wikipedia.org/wiki/HAKMEM HAKMEM from Wikipedia]
* [http://www.jjj.de/fxt/fxtbook.pdf Matters Computational - ideas, algorithms, source code] (pdf) Ideas and Source Code by [[Mathematician#Arndt|Jörg Arndt]]
* [http://aggregate.org/MAGIC The Aggregate Magic Algorithms] by [[Hank Dietz]]
* [http://graphics.stanford.edu/%7Eseander/bithacks.html Bit Twiddling Hacks] by [http://graphics.stanford.edu/%7Eseander/ Sean Eron Anderson]
* [http://bits.stephan-brumme.com/ the bit twiddler] by [http://www.stephan-brumme.com/ Stephan Brumme]
* [http://programming.sirrida.de Programming pages] of [http://sourceforge.net/users/jasper_neumann/ Jasper Neumann]
* [https://github.com/keon/awesome-bits GitHub - keon/awesome-bits: A curated list of awesome bitwise operations and tricks]
* [http://www.onjava.com/pub/a/onjava/2005/02/02/bitsets.html Bitwise Optimization in Java: Bitfields, Bitboards, and Beyond] by [[Glen Pepicelli]], 2005, [https://en.wikipedia.org/wiki/O%27Reilly_Media O'Reilly's] [http://onjava.com/ OnJava.com] » [[Java]], [[Bitboards]]
* [https://github.com/golang/go/issues/18616 math/bits: an integer bit twiddling library · Issue #18616 · golang/go · GitHub] » [[Go (Programming Language)]]
=External Links=
* [https://en.wikipedia.org/wiki/Bit_twiddler Bit twiddler from Wikipedia]
* [https://en.wikipedia.org/wiki/Bit_manipulation Bit manipulation from Wikipedia]
* [http://mridulm.blogspot.com/2006/09/bit-twiddling.html bit twiddling ...] from [http://mridulm.blogspot.com/ Random thoughts] blog by [[Mridul Muralidharan]]
* [http://zimbry.blogspot.de/ Twiddling the Bits] by [[David Stafford]]
* [[Videos#NHOP|NHØP]] & [[Videos#TaniaMaria|Tania Maria]] - Baião improvisado, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=7zbY6URSZ-U|alignment=left|valignment=top}}
'''[[Programming|Up one Level]]'''
