Simulating int arithmetic with wrap-around
Steve D'Aprano
steve+python at pearwood.info
Fri Dec 30 09:47:32 EST 2016
It's easy to simulate integer arithmetic with wrap-around for *unsigned*
ints. For example, imagine a four-bit integer (0 through 15):
# Addition
py> (7 + 8) & 0xF
15
py> (7 + 9) & 0xF
0
py> (7 + 10) & 0xF
1
# Multiplication
py> (7 * 2) & 0xF
14
py> (7 * 3) & 0xF
5
py> (7 * 4) & 0xF
12
And in general, for any operator ⊗, and a and b both in the range 0 through
2**N-1, we can simulate unsigned N-bit integer arithmetic with:
a⊗b & (2**N - 1)
(I think this works for all the arithmetic operators, and the bitwise
operations. The bitmask & 2**N-1 is not needed for the bitwise operations
except for left-shift.)
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?
Signed arithmetic also has some gotchas. For example, -x is not necessarily
defined, nor is abs(x).
Thanks,
--
Steve
“Cheer up,” they said, “things could be worse.” So I cheered up, and sure
enough, things got worse.
More information about the Python-list
mailing list