[docs] [issue29710] Incorrect representation caveat on bitwise operation docs

[Mark Dickinson]

Mark Dickinson <dickinsm at gmail.com> 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 <report at bugs.python.org>
<https://bugs.python.org/issue29710>
_______________________________________