Mark Dickinson <[email protected]> added the comment:
> “Bitwise operations have the same result as calculations using two’s
> complement with a bit-width large enough to avoid overflows.”
That sounds fine to me, but then, the original wording sounds fine to me now
that I know how to read it. :-) The main issue here is making it clear that in
"avoid overflow", we're talking about overflow incurred in representing a value
in two's complement in the first place, as opposed to overflow of the operation
itself.
I'd go with something like the following (which evolved by successive
refinement from Martin's suggestion):
"Each bitwise operation has the same result as though carried out in two's
complement using a bit-width that's large enough to represent the inputs."
> I presume this is what your “2-adic representation” is.
Yes, exactly. Without invoking 2-adic numbers, which is a bit of overkill,
there's a natural one-to-one correspondence between
(a) integers, and
(b) (singly) infinite bit strings, extending infinitely to the left, in which
either all but finitely many bits are zero, or all but finitely many bits are
one.
In the domain (b), the bitwise operations have their obvious bitwise meanings;
translating via the correspondence gives us the corresponding definitions of
the bitwise operations on (a).
For the correspondence: going from (a) to (b): take an integer n, then for each
k >= 0 reduce n modulo 2^k to get a length-k bit string. Now it's easy to see
that the length-k bit strings are all compatible with one another, in the sense
that they all agree with each other when right-aligned, so you naturally get an
infinite-length bit string that's eventually either all 1s (for negative n) or
all zeros (for nonnegative n).
Going back from (b) to (a): it's not hard to convince yourself that the map
above is one-to-one and onto, but then you miss out on a beautiful description
of the inverse map: given an infinite bit-string indexed as below, with b_0 the
least significant bit:
... b_{k+1} b_k b_{k-1} ... b_2 b_1 b_0
we simply map that bit string to the integer
n = sum_{i>=0} b_i * 2**i
Of course the RHS of the above is an infinite sum, so a priori doesn't make
sense. If almost all the bits are zeros, it becomes a finite sum and
everything's okay. If almost all the bits are ones, you can either (i)
introduce the 2-adic topology on the integers and point out that it still
converges in that topology, so that everything has a sound mathematical
footing, or (ii) just use the "trick" that 1 + 2 + 4 + 8 + 16 + ... = -1, which
more-or-less amounts to the same thing.
----------
_______________________________________
Python tracker <[email protected]>
<https://bugs.python.org/issue29710>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
