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.

Is XOR Distributive over Addition?

Google search console has become a thing of mild interest to me since I moved my website and Google forgot my content existed. Impressions – search terms that match your site but don’t lead to a click – can provide fascinating insights into the Internet habits of others, particularly when the content is completely irrelevant to the query. Impressions are the best place to look for these noisy mismatches. I looked at my top ten impressions and was pleased to see my stalkers (people who type my name into Google) are outnumbered by CBOR enthusiasts. The world needs to must pay more attention to CBOR. These search terms are:

is xor associative over addition?

The highlighted term “is xor distributive over addition” jumped out at me.

Since multiplication obviously does distribute over addition (ignoring overflow), it’s perhaps a reasonable question to ask. To disprove this proposition, it is enough to find a single counterexample (not hard, and much quicker than a google search) but it’s more interesting to find a constructive class of counterexamples. I thought of a few strategies to disprove this, other than picking random numbers and checking, that I thought were worth writing down.

Tangentially, on the topic of Google relevance, this search term had nothing to do with this blog until this post, but when I search for topics I think my posts are related to, I can’t find them. I expect not to be seeing “is xor distributive over addition” in the search console in future.

Complement Argument

Would XOR distribute over the addition of a number and its logical complement? We would have that y ^ (x + ~x) = y ^ x + y ^ ~x for any y. Then we have y ^ -1 = ~y = y ^ x + y ^ ~x. So based on the assumption of distributivity, y ^ x + y ^ ~x must have none of the bits from y. We have a contradiction because it is clear that all of the bits in y ^ x + y ^ ~x are set.

Left Shift Argument

Addition causes digits to carry left when the bits in the same position are both set, so x + x is equivalent to x << 1 (ignoring overflow). If, for any integer y, we had that y ^ (x + x) = y ^ x + y ^ x we can find constraints on this identity by considering either the rightmost unset bit or the leftmost set bit of x in isolation. Considering the rightmost set bit at position p: this bit is set on the LHS of this identity if and only if it is unset in y. On the RHS, it is set iff its leftmost neighbour at position p-1 is unset in y, because we shift y ^ x to the left. So we can construct counterexamples whenever p and p-1 differ, and the proposition is not generally true.