Timeline for Prove HAKMEM Item 23: connection between arithmetic operations and bitwise operations on integers
Current License: CC BY-SA 4.0
14 events
when toggle format | what | by | license | comment | |
---|---|---|---|---|---|
Apr 5, 2023 at 15:33 | comment | added | Ntwali B. | @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}$. | |
Apr 5, 2023 at 15:19 | history | edited | John L. | CC BY-SA 4.0 |
Fixed typos. Added two's complement with infinite length.
|
Apr 5, 2023 at 14:17 | comment | added | Sneftel | IMO an easy way to extend the proof to two's complement integers is to show that the result holds for (unsigned) addition modulo 2^n, then demonstrate the equivalence of that to two's complement. Two's complement arithmetic is really just carefully biased modular arithmetic. | |
Apr 5, 2023 at 6:05 | comment | added | John L. | It looks a proof wanted at the end of this answer is given in Hacker's Delight section 2-1 and 2-2 if we assume the specification of Java or Python can fit in. | |
Apr 5, 2023 at 5:36 | history | edited | John L. | CC BY-SA 4.0 |
Another modern interpretation.
|
Apr 5, 2023 at 4:45 | comment | added | hobbs | I'm not conversant enough in the relevant bits of math to enumerate the conditions exactly, but I think it's basically: any chain of operations involving only addition, subtraction, and, or, and xor is "safe" provided that the "true result" of that chain is in the representable range [even if the intermediate values are not], and other operations (like multiplication) are safe if they consume only safe values and don't overflow themselves. | |
Apr 5, 2023 at 4:37 | comment | added | hobbs | @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 :) | |
Apr 4, 2023 at 23:40 | vote | accept | Ntwali B. | ||
Apr 4, 2023 at 23:40 | comment | added | Ntwali B. | To my shame, I should have written the expansion as you did and the proof would have been obvious, thank you for spelling it out! For it's worth, I took a different route after my last comment: prove that for $A = 1$ and $B = 0$ we have $A + B = 1$. Then assume Peano's axioms, that is $1 = successor(0)$ and so on for any $B$ in $\mathbb{N}$. It then becomes sufficient to show that $A + (B + 1) = (A + B) +1$, which is trivial. But I still like your proof better as it is very explicit and it is exactly what I was looking for. | |
Apr 4, 2023 at 22:40 | comment | added | hobbs | 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. | |
Apr 4, 2023 at 19:58 | comment | added | John L. | @NtwaliB. Is my updated answer clear enough? | |
Apr 4, 2023 at 19:55 | history | edited | John L. | CC BY-SA 4.0 |
More explanation.
|
Apr 4, 2023 at 18:59 | comment | added | Ntwali B. | 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. | |
Apr 4, 2023 at 15:24 | history | answered | John L. | CC BY-SA 4.0 |