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
Bit-Twiddling related to Bitboards
- 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
HAKMEMC -- HAKMEM Programming hacks in C by Alan Mycroft
- 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