5
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ You are not converting arithmetic addition to bit operations because you have a regular arithmetic + on the right as well. You can't get away from that because addition can carry and the bitwise operations do not. For example, let $A=B=1$. Then your expression becomes $1+1=1+1=0+2\cdot 1$ The first is no simplification. The second still has an addition in it and a multiply as well. The multiply could become a bit shift. $\endgroup$ Apr 5, 2023 at 14:47
  • $\begingroup$ There is a fourth simple expression, $2(A\mid B)-(A\oplus B)$ besides $A + B$, $(A\operatorname{\&} B) + (A\mid B)$, $(A\oplus B) + 2(A\operatorname{\&} B)$. $\endgroup$
    – John L.
    Apr 5, 2023 at 15:30
  • $\begingroup$ @RossMillikan yes, that's why I was having trouble in my initial attempts. I was trying to derive the formula and failed (and that's the genius of Schroeppel, not sure how he came up with this). But John L. gave the proof I was looking for. Of course, I'm still wondering how Schroeppel came up with this in the first place :-) $\endgroup$
    – Ntwali B.
    Apr 5, 2023 at 15:43
  • 1
    $\begingroup$ @JohnL. yes, that one's also in Hacker's Delight. I referenced it so that an actual answer doesn't start from either of these. $\endgroup$
    – Ntwali B.
    Apr 5, 2023 at 15:44
  • $\begingroup$ $(A \operatorname{\&} B) + (A \mid B)$ looks a bit silly, it seems to read "for each bit position, if either A or B has the bit set, count one, then if both are set, count one more". That's how arithmetic works, but it seems a bit convoluted a way of putting it. $\endgroup$
    – ilkkachu
    Apr 6, 2023 at 4:38

5 Answers 5

6
$\begingroup$

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?

$\endgroup$
9
  • $\begingroup$ Thank you for the clarification on the interpretation. I'm still not able to fully appreciate the entirety of the reservations you point when dealing with negative $A$ or $B$ but will comment here (or ask a separate question) after I've given it more thought. As for the proof, it makes sense that we consider $A, B$ in $\mathbb{B}$ as being enough. But it is taking me some time to convince myself that it is indeed enough :-). Will comment again with either additional clarification request or a thank you comment and accept the answer. $\endgroup$
    – Ntwali B.
    Apr 4, 2023 at 18:59
  • 1
    $\begingroup$ @NtwaliB. Is my updated answer clear enough? $\endgroup$
    – John L.
    Apr 4, 2023 at 19:58
  • 6
    $\begingroup$ You can imagine negative numbers having an "infinity of ones off to the left" the same way positive numbers have zeroes, and use twos-complement without having to tie yourself to a particular word size. I think the HAKMEM group would have been comfortable with that idea; it's semi-jokingly implied in HAKMEM 154. $\endgroup$
    – hobbs
    Apr 4, 2023 at 22:40
  • 1
    $\begingroup$ @JohnL. basically, the overflow behavior you were worried about is actually pretty benign, and gives you the same answer as infinite width under certain conditions, and we're staying within those conditions. One of the reasons why it's the dominant form of arithmetic on computers :) $\endgroup$
    – hobbs
    Apr 5, 2023 at 4:37
  • 1
    $\begingroup$ @JohnL. I think your proof carries easily to two's complement (which is what Java and Python use): an integer $A$ in $\mathbb{Z}$ has two's complement representation $A = -A_{n-1} 2^{n-1} + \sum_{i=0}^{n-2} A_i2^{i}$. We use the procedure you have outlined above for the two parts of the formula above. The sum $\sum_{i=0}^{n-2} A_i2^{i} + \sum_{i=0}^{n-2} B_i2^{i}$ is already proved above. We do the procedure again for the sign part $-A_{n-1} 2^{n-1} -B_{n-1} 2^{n-1}$, keeping in mind that $-0 \equiv 0$ and $-1 \equiv 11$. And that's it. The formula holds for $A, B$ in $\mathbb{Z}$. $\endgroup$
    – Ntwali B.
    Apr 5, 2023 at 15:33
5
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$).

$\endgroup$
-2
$\begingroup$

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.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.