Bit Twiddling Blog Posts
This is a list of blog posts to read if you like bit twiddling and some basic maths. I would like to improve this list over time – if you have a post similar to these please provide a link in the comments.
- Table of basic reversible integer operations – Marc B. Reynolds looks at several bijective functions on the integers modulo 32.
- Modular multiplicative inverses – multiplication of integers modulo 32 is invertible for odd integers. Daniel Lemire derives this property and constructs an efficient algorithm to compute the modular inverse of an odd integer.
- Carryless multiplicative inverse – A guy called Harold demonstrates an algorithm for computing the carryless inverse of integers modulo 32.
- Visualizing Addition, Subtraction and Complement – A spatial interpretation of the addition, subtraction and complement operations on bitwise integers. Another Harold special.
- XOR rotates and their inverses – Marc B. Reynolds looks at XOR rotates, their inverses and provides a few visualisations.
- Is XOR distributive over addition – a simple proof by contradiction that XOR does not distribute over addition.
- Parallel prefix/suffix operations – more insight into compression operations from Harold.
- Morton Codes and bit interleaving – Jeroen Baert discusses implementations of Z-curves through bit interleaving.
- Tesseral Arithmetic – cracking open Morton encoded coordinates to perform arithmetic adds overhead and reduces throughput. Harold discusses and implements arithmetic without leaving the Morton encoding domain.
- Hyperplanes and Wildcards David Eppstein interprets bit strings as the vertices of hypercubes, and develops a wildcard concept to represent unspecified dimensions. This is very similar in concept to a rule engine I wrote recently.