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.

  1. Table of basic reversible integer operations – Marc B. Reynolds looks at several bijective functions on the integers modulo 32.
  2. 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.
  3. Carryless multiplicative inverse – A guy called Harold demonstrates an algorithm for computing the carryless inverse of integers modulo 32.
  4. Visualizing Addition, Subtraction and Complement – A spatial interpretation of the addition, subtraction and complement operations on bitwise integers. Another Harold special.
  5. XOR rotates and their inverses – Marc B. Reynolds looks at XOR rotates, their inverses and provides a few visualisations.
  6. Is XOR distributive over addition – a simple proof by contradiction that XOR does not distribute over addition.
  7. Parallel prefix/suffix operations – more insight into compression operations from Harold.
  8. Morton Codes and bit interleaving – Jeroen Baert discusses implementations of Z-curves through bit interleaving.
  9. 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.
  10. 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.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>