Bit-Twiddling

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.

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

• ABM
• BMI1
• BMI2
• General Setwise Operations
• TBM

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:

• Preprints of Recent Papers including dancing links
• The Art of Computer Programming

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

HAKMEM from Wikipedia

• 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

Up one Level