Prove HAKMEM Item 23: connection between arithmetic operations and bitwise operations on integers

Question

Prove that for $A, B \in \mathbb{Z}$, $A + B = (A \operatorname{\&} B) + (A \mid B) = (A \oplus B) + 2(A \operatorname{\&} B)$ where $\&$ is bitwise AND, $|$ is bitwise OR and $\oplus$ is bitwise XOR. (It is reasonable to assume that the bit representation of integers is two's complements.)

The statement above appears as item 23 of HAKMEM but it is given without proof. Its significance lies in the fact that it connects arithmetic operators on integers with bitwise operators.

Following definitions in The Art of Computer Programming, Volume 4A, Part 1, define bitwise operations on nonnegative integers as follow:

Let $A = (...A_3A_2A_1)$, $B = (...B_3B_2B_1)$, and $C = (...C_3C_2C_1)$. We have

$$ \begin{gather} A \operatorname{\&} B = C \iff A_k \wedge B_k = C_k; \text{ for all } k \geq 0\\ A \mid B = C \iff A_k \vee B_k = C_k; \text{ for all } k \geq 0\\ A \oplus B = C \iff A_k \oplus B_k = C_k; \text{ for all } k \geq 0 \end{gather} $$

Our goal then is using the definitions above together with the definition of addition on bit strings to prove item 23 of HAKMEM; if possible.

Note: as stated earlier, there are other relations between bitwise operators and arithmetic operators from which the statement above can be deduced (and vice-versa), see subsection $2{-}2$ of Hacker's delight for such relations. That's not what we want. We want to prove the statement from "first principles", not from equivalent relations; if possible.

I'm unable to construct a proof, as in the starting point is not obvious (to me). And everywhere I have looked online it is stated without proof.

Answer 1

Bitlength and bound needed for two's complement

Prove that for $A, B \in \mathbb{Z}$, $A + B$ $= (A\operatorname{\&}B) + (A \mid B)$ $= (A \oplus B) + 2(A\operatorname{\&}B)$ where $\operatorname{\&}$ is bitwise AND, $\mid$ is bitwise OR and $\oplus$ is bitwise XOR. (It is reasonable to assume that the bit representation of integers is two's complement.)

You have interpreted item 23 so that it is almost correct.

If we allow $A$ or $B$ to be negative, however, it is hard/impossible to assign/determine the sign of $A\operatorname{\&}B$, $A\mid B$ or $A\oplus B$ if we use the natural/standard representation of a number in base $2$. A different method that can represent signed integers without using the sign $\pm$ has to come into play. You selected two's complement. Then means you should also specify the length of a binary representation as well as restrict the magnitude of $A$ and $B$ to avoid overflow. That kind of specification and restriction is unlikely to be the intention of Rich Schroeppel, the author of this standalone item.

---

On the other hand, the equalities hold for all integers if integers are represented by two's complement with infinite length, as mentioned by hobbs and the Wikipedia article Two's complement and 2-adic numbers.

Let $A$ and $B$ be nonnegative integers

Here is a simpler way to interpret item 23. The only change is $A$ and $B$ are natural numbers (including $0$) instead.

For all $A, B \in \Bbb N$, $\ A + B$ $= (A\operatorname{\&}B) + (A\mid B)$ $= (A \oplus B) + 2(A\operatorname{\&}B)$ where $\operatorname{\&}$ is bitwise AND, $\mid $ is bitwise OR and $\oplus$ is bitwise XOR.

---

Let us prove the proposition above.

Suppose the usual binary representation $A$ and $B$ are $\cdots A_2A_1A_0$ and $\cdots B_2B_1B_0$ respectively, where all $A_k$'s and $B_k$'s are either $0$ or $1$. By the definition of bitwise operations as given in the question (or everywhere else), $$\begin{aligned} &\qquad(A\operatorname{\&}B) + (A \mid B)\\ &= \left(\cdots + (A_2 \& B_2)2^2+(A_1 \& B_1)2^1+(A_0 \& B_0)\right)\\ &\quad + \left(\cdots + (A_2 | B_2)2^2+ (A_1 | B_1)2^1+(A_0 | B_0)\right)\\ &= \cdots \\ &\quad+ ((A_2 \& B_2)+(A_2 | B_2))2^2\\ &\quad+ ((A_1 \& B_1)+(A_1 | B_1))2^1 \\ &\quad+ ((A_0 \& B_0)+(A_0 | B_0))\\ \end{aligned}$$

We have a similar identity for $(A\oplus B) + 2(A\operatorname{\&}B)$.

Note that $A+B$ also means doing addition place-wise as shown in the following identity.

$$\begin{aligned} A+B&=\cdots\\ &+(A_2 + B_2)2^2\\ &+(A_1 + B_1)2^1\\ &+(A_0 + B_0)\\ \end{aligned}$$

So it is enough to prove the following identities. $$\begin{aligned} &\ \ \vdots\\ A_2+B_2 &=(A_2 \& B_2)+(A_2 | B_2)\\ A_1+B_1 &=(A_1 \& B_1)+(A_1 | B_1)\\ A_0+B_0 &=(A_0 \& B_0)+(A_0 | B_0)\\ \end{aligned}$$

That is, it is enough to show the proposition is true when both $A$ and $B$ are either $0$ or $1$.

There are $4$ cases.

• $A=B=1$. Then
  $A+B=2$
  $(A\operatorname{\&}B) + (A\mid B) = 1+1=2$
  $(A \oplus B) + 2(A\operatorname{\&}B)=0+2\cdot1=2$
• I am sure you will be able to verify the other three cases.

Another interpretation, $A$ and $B$ are integers in programming languages

Consider Java. If A and B are of type int or long, then (A & B) + (A | B) and (A ^ B) + 2 * (A ^ B) are all equal. It does not matter whether A and/or B is negative and whether there is overflow. For example, if int A = (1 << 30) + (1 << 29); int B = A - 1;, then A + B, (A & B) + (A | B) and (A ^ B) + 2 * (A ^ B) are all equal to -1342177280.

Consider Python. If $A$ and $B$ are of type <class 'int'> in Python, then those three expressions are also equal. It does not matter whether A and/or B is negative.

I would believe the same happens for most programming languages.

It is easy to expect/understand the expressions are equal when none of A and B are negative and there is no overflow. To understand why they remain equal without exception otherwise, it may require some digging into the specification/implementation of Java/Python. Or, where is an existing proof?

Answer 2

This answer isn't rigorous or starting from first principles, but I thought this was elegant so here it is anyway.

Given that addition is commutative and associative and bit-shifting all summands left also bit-shifts the result by the same amount, and that $(...A_3A_2A_1) = ... + A_300 + A_20 + A_1$, we have that $(...C_3C_2C_1) = ...+(A_3+B_3)00+(A_2+B_2)0+(A_1+B_1)$. To prove that $X+Y=A+B$ we only have to prove that for all $n$, $X_n+Y_n=A_n+B_n$.

We can brute-force that by drawing a truth table and we are done, but it's more interesting to observe that $A_n+B_n$ counts the number of 1 bits among $A_n$ and $B_n$ - that is 0, 1 or 2 (10). This is invariant to permutations of the summand bits.

Therefore, any bitwise transformation that preserves the number of 1 bits in each position $n$ will also preserve the sum $C$.

Example:

    10101010     
  + 00110011 = 11011101
    ^^^^^^^^
    10211021 <- number of bits in each column above and below
    vvvvvvvv
    00110010
  + 10101011 = 11011101
    ^  ^^ ^
    bits swapped in columns, same answer

This also works for addition of 3 or more numbers.

 

The transformation $(A_n, B_n) \Longrightarrow (A_n\land B_n, A_n\lor B_n)$ preserves the total number of 1s, but shifts them preferentially towards the right half (10 becomes 01, everything else is unchanged).

The transformation $A_n\lor B_n \Longrightarrow (A_n\land B_n,A_n\oplus B_n)$ also preserves the total number of 1s, since both halves can't be 1 at the same time.

Answer 3

Consider the addition of two random binary numbers like these: $$ \begin{matrix} &00101011& (A)\\ + &01100101& (B)\\\hline = &10010000& (A+B) \end{matrix} $$

Ignore the signed vs unsigned problem for now.

Now, $1$s are heavier than $0$s, so if a $1$ in $A$ is on top of a $0$ in $B$, they swap places:

$$ \begin{matrix} &00100001& (C)\\ + &01101111& (D)\\\hline = &10010000& (C+D) \end{matrix} $$

You should agree that swapping digits like this doesn't affect the final sum, so $A+B=C+D$. But what are $C$ and $D$?

The only way there can be a $1$ in $C$ is if there are $1$s in that position in both $A$ and $B$. In other words $C=(A \& B)$.

In $D$, on the other hand, there can be a $1$ if there a $1$ already in $B$ or if one is swapped in from $A$ above. In other words $D=(A|B)$

Adding it all up, $$A+B = (A\&B) + (A|B)$$

First half is done. The second half is harder to picture, but I will try.

Returning to our original addition above, start by adding the digits without carry: $$ \begin{matrix} &00101011& (A)\\ +? &01100101& (B)\\\hline = &01201112& A+B ? \end{matrix} $$

What we have here is an non-normalized number, where digits can have values that are larger than the base. Think of it as having one dollar bill and 231 one-cent coins. Perfectly valid, but you will feel more comfortable if you can get more bills and fewer coins. The point here is that the sum is $A+B$, only written in an unusual way.

So, lets make change. For every 2, we write 0 and 1 in carry.

$$ \begin{matrix} &\centerdot 01201112&(nonnormal) A+B\\\hline &00100001\centerdot& carries\\ + &\centerdot 01100101& values\\\hline = &010010000& (normalized) A+B \end{matrix} $$ (Please pretend that aligns properly)

The $carries$ line contain a $1$ if there was a $2$ in the non-normalized number in the column to the right, which means there must have been $1$s in both $A$ and $B$. The shift to the left is the same as multiplying by two.

The $values$ line contain a $1$ if the non-normalized number has a $1$ in that column, which means that either $A$ or $B$ has a $1$ there, but not both.

Adding it all up gives us $$A+B = 2(A\&B) + (A\oplus B)$$

Shuffle the terms and put it together with the first half and you have the statement you wanted to prove.

Answer 4

It is an easy matter to check these identity that are true for single bits (the case $1+0$ follows by commutativity).

$$0+0=0\land0+0\lor0=0\oplus0+2\,(0\land0)\\ 0+1=0\land1+0\lor1=0\oplus1+2\,(0\land1)\\ 1+1=1\land1+1\lor1=1\oplus1+2\,(1\land1)$$

And these results immediately generalize to bitwise operations by linearity, as the value of a binary number is a linear combination of its bits (with coefficients equal to powers of $2$).

Answer 5

Prove it for the cases that A and B are both true, that exactly one of them is true, and that none of them is true.