Simulating int arithmetic with wrap-around

[Chris Angelico]

On Sat, Dec 31, 2016 at 1:47 AM, Steve D'Aprano
<steve+python at pearwood.info> wrote:
> How about *signed* integers?
>
> 7 + 1 => -8
> 7 + 2 => -7
> 7 + 7 => -2
>
> 7 * 2 => -2
> 7 * 3 => 5
> 7 * 4 => -4
>
>
> Again, assume both operands are in range for an N-bit signed integer. What's
> a good way to efficiently, or at least not too inefficiently, do the
> calculations in Python?

One way would be to work with the integers as unsigned numbers, and
then render them signed for display only. The neat thing about two's
complement (as opposed to two's compliment, which is a really sweet
thing to say to someone) is that a lot of operations work exactly the
same way. You add 7+2 and get 9, and then display 9 as -7. You take
that 9 (really -7) and add 5 to it, and you get 14, which you display
as -2. Add another 4 and you get 18, mask that off and you get 2. You
may have to handle multiplication and division differently, I think,
and you might need a sign-extend right shift operator (as opposed to a
zero-fill right shift), but they should be able to be defined in terms
of the other operations.

7 * 2 => 14, displayed as -2
7 * 3 => 21, mask to 5
7 * 4 => 28, mask to 12, display as -4
7 * 9 => 63, mask to 15, display as -1. Conceptually 7*-7 => -49.

Actually you might be able to get away with multiplication perfectly.
I'm thinking of the Intel 80x86 opcodes, where MUL and IMUL are
unsigned and signed multiplication, respectively, but they differ
because the result is twice as wide as the operands (eg if you
multiply two 16-bit numbers, you get a 32-bit result). The Intel chips
do the same with division (eg you divide a 32-bit number by a 16-bit
and get back a 16-bit quotient and 16-bit remainder). You may be able
to take the exact same short-cut.

> Signed arithmetic also has some gotchas. For example, -x is not necessarily
> defined, nor is abs(x).

AIUI -x is always defined, but might be equal to x in two
circumstances (zero and MAXINT+1). Not sure about abs(x), but probably
would be the same.

ChrisA