#### 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 about my content. Impressions – search terms that match your site but don’t lead to a click – are full of fascinating false positives. I looked at some of my impressions. These search terms are:

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.