Difference between revisions of "Bit-Twiddling"
GerdIsenberg (talk | contribs) (Created page with "'''Home * Programming * Bit-Twiddling''' '''Bit-twiddling''' is a family of techniques used in [https://en.wikipedia.org/wiki/Bit_manipulation manipulating]...") |
GerdIsenberg (talk | contribs) |
||
| (3 intermediate revisions by the same user not shown) | |||
| Line 31: | Line 31: | ||
* [http://www-cs-faculty.stanford.edu/%7Eknuth/fasc0c.ps.gz Pre-Fascicle 0c (Boolean evaluation)] | * [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)] | * [http://www-cs-faculty.stanford.edu/%7Eknuth/fasc1a.ps.gz Pre-Fascicle 1a (Bitwise tricks and techniques)] | ||
| − | Online | + | 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] | * [[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/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] | * [http://www.hackersdelight.org/hdcode.htm C code for most of the programs that appear in HD] | ||
=Other Bit-Twiddling resources= | =Other Bit-Twiddling resources= | ||
| − | * Michael Beeler, [[Bill Gosper]], [https://en.wikipedia.org/wiki/Richard_Schroeppel Rich Schroeppel] ('''1972'''). ''[ | + | * Michael Beeler, [[Bill Gosper]], [https://en.wikipedia.org/wiki/Richard_Schroeppel Rich Schroeppel] ('''1972'''). ''[https://dspace.mit.edu/handle/1721.1/6086 HAKMEM]'', Memo 239, Artificial Intelligence Laboratory, [[Massachusetts Institute of Technology]] |
| − | |||
: [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] | : [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] | : [https://en.wikipedia.org/wiki/HAKMEM HAKMEM from Wikipedia] | ||
| Line 46: | Line 45: | ||
* [http://programming.sirrida.de Programming pages] of [http://sourceforge.net/users/jasper_neumann/ Jasper Neumann] | * [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] | * [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://web.archive.org/web/20050205014648/http://www.onjava.com/pub/a/onjava/2005/02/02/bitsets.html Bitwise Optimization in Java: Bitfields, Bitboards, and Beyond] by [[Glen Pepicelli]], ([https://en.wikipedia.org/wiki/Wayback_Machine Wayback Machine], 2005), [http://en.wikipedia.org/wiki/O%27Reilly_Media O'Reilly's] [https://web.archive.org/web/20050203015229/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)]] | * [https://github.com/golang/go/issues/18616 math/bits: an integer bit twiddling library · Issue #18616 · golang/go · GitHub] » [[Go (Programming Language)]] | ||
| Line 54: | Line 53: | ||
* [http://mridulm.blogspot.com/2006/09/bit-twiddling.html bit twiddling ...] from [http://mridulm.blogspot.com/ Random thoughts] blog by [[Mridul Muralidharan]] | * [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]] | * [http://zimbry.blogspot.de/ Twiddling the Bits] by [[David Stafford]] | ||
| − | * [[ | + | * [[:Category:NHOP|NHØP]] & [[:Category:Tania Maria|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}} | : {{#evu:https://www.youtube.com/watch?v=7zbY6URSZ-U|alignment=left|valignment=top}} | ||
'''[[Programming|Up one Level]]''' | '''[[Programming|Up one Level]]''' | ||
| + | [[Category:NHOP]] | ||
| + | [[Category:Tania Maria]] | ||
Latest revision as of 12:07, 3 February 2022
Home * Programming * Bit-Twiddling
Bit-twiddling is a family of techniques used in 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, but there are both easy-to-read bitboard implementations and difficult-to-read implementations of other board representations.
Contents
- BitScan
- Flipping Mirroring and Rotating
- Kogge-Stone
- Obtaining and Clearing the Least Significant Bit (LS1B)
- Population Count
- Traversing Subsets of a Set
Bit-Manipulation
Forum Posts
- Bit twiddlement question: greater of two popcounts by Zach Wegner, CCC, August 06, 2009
- Bit twiddling question, part 2: arbitrary bitscan order by Zach Wegner, CCC, August 11, 2009
- Bit position hack by nak3c, OpenChess Forum, September 01, 2013
Important online resources
Online Papers by Donald Knuth:
- Vol 4 as Pre-Fascicle PostScripts:
- Pre-Fascicle 0b (Boolean basics)
- Pre-Fascicle 0c (Boolean evaluation)
- Pre-Fascicle 1a (Bitwise tricks and techniques)
Online Papers by Henry S. Warren, Jr.
- Hacker’s Delight, 2nd Edition
- Sample section of Hacker's Delight, Chapter 2 Basics (pdf)
- C code for most of the programs that appear in HD
Other Bit-Twiddling resources
- Michael Beeler, Bill Gosper, Rich Schroeppel (1972). HAKMEM, Memo 239, Artificial Intelligence Laboratory, Massachusetts Institute of Technology
- Matters Computational - ideas, algorithms, source code (pdf) Ideas and Source Code by Jörg Arndt
- The Aggregate Magic Algorithms by Hank Dietz
- Bit Twiddling Hacks by Sean Eron Anderson
- the bit twiddler by Stephan Brumme
- Programming pages of Jasper Neumann
- GitHub - keon/awesome-bits: A curated list of awesome bitwise operations and tricks
- Bitwise Optimization in Java: Bitfields, Bitboards, and Beyond by Glen Pepicelli, (Wayback Machine, 2005), O'Reilly's OnJava.com » Java, Bitboards
- math/bits: an integer bit twiddling library · Issue #18616 · golang/go · GitHub » Go (Programming Language)
External Links
- Bit twiddler from Wikipedia
- Bit manipulation from Wikipedia
- bit twiddling ... from Random thoughts blog by Mridul Muralidharan
- Twiddling the Bits by David Stafford
- NHØP & Tania Maria - Baião improvisado, YouTube Video
