Friday 22 July 2022

Bit-level commutativity and "sum gap" revisited

In an earlier post, bit-level commutativity, it was shown that addition is not only invariant under swapping the operands, but also under swapping individual bits between the operands, provided that they are of equal place-value. For example the least significant bits of the operands of a sum could be exchanged without changing the value of the sum. Bit-level commutativity of addition implies that A + B = (A & B) + (A | B).

In the range a sum cannot fall within, it was shown that the "gap" which a sum cannot fall within can be widened from: $$A + B \begin{cases} \ge \max(A,B) & \text{ if addition does not carry} \\ \le \min(A,B) & \text{ if addition does carry} \end{cases}\tag{Eq1}$$ To: $$A + B \begin{cases} \ge A\:|\:B & \text{ if addition does not carry} \\ \le A\:\&\:B & \text{ if addition does carry} \end{cases}\tag{Eq2}$$ This makes the gap wider because A & B is often less than min(A, B), and A | B is often greater than max(A, B).

To start with, let's assume that $$A + B \begin{cases} \ge A & \text{ if addition does not carry} \\ \le A & \text{ if addition does carry} \end{cases}\tag{Eq3}$$ Since addition is commutative, the roles of A and B could be exchanged without affecting the truth of equation Eq3, so this must also hold: $$A + B \begin{cases} \ge B & \text{ if addition does not carry} \\ \le B & \text{ if addition does carry} \end{cases}\tag{Eq4}$$ If A + B is greater than or equal to both A and B, then it must also be greater than and equal to max(A, B), and a similar argument applies to the upper bound. Therefore, Eq1 follows from Eq3.

Substituting A and B with A & B and A | B (respectively) in Eq3 and Eq4 gives $$(A\:\&\:B) + (A\:|\:B) \begin{cases} \ge (A\:\&\:B) & \text{ if addition does not carry} \\ \le (A\:\&\:B) & \text{ if addition does carry} \end{cases}\tag{Eq5}$$ And $$(A\:\&\:B) + (A\:|\:B) \begin{cases} \ge (A\:|\:B) & \text{ if addition does not carry} \\ \le (A\:|\:B) & \text{ if addition does carry} \end{cases}\tag{Eq6}$$ Picking the "does carry" case from Eq5 and the "does not carry" case from Eq6, and using that A + B = (A & B) + (A | B), gives Eq2.