[issue29710] Incorrect representation caveat on bitwise operation docs
New submission from Nick Coghlan: The docs on bitwise operations at https://docs.python.org/3/library/stdtypes.html#bitwise-operations-on-intege... include the caveated sentence: Negative numbers are treated as their 2’s complement value (this assumes that there are enough bits so that no overflow occurs during the operation). This sentence isn't correct now that integers are always arbitrary length. The bitwise inversion will never overflow, and is instead calculated as "-(n+1)" rather than literally flipping bits in the representation: https://docs.python.org/3/reference/expressions.html#unary-arithmetic-and-bi... ---------- assignee: docs@python components: Documentation messages: 288890 nosy: docs@python, ncoghlan priority: normal severity: normal stage: needs patch status: open title: Incorrect representation caveat on bitwise operation docs type: enhancement versions: Python 3.5, Python 3.6, Python 3.7 _______________________________________ Python tracker <report@bugs.python.org> <http://bugs.python.org/issue29710> _______________________________________
Sanyam Khurana added the comment: Hi, I'm working on this issue. ---------- nosy: +CuriousLearner _______________________________________ Python tracker <report@bugs.python.org> <http://bugs.python.org/issue29710> _______________________________________
Changes by Wolfgang Maier <wolfgang.maier@biologie.uni-freiburg.de>: ---------- nosy: +wolma _______________________________________ Python tracker <report@bugs.python.org> <http://bugs.python.org/issue29710> _______________________________________
Mark Dickinson added the comment:
This sentence isn't correct now that integers are always arbitrary length.
It's not really clear what that line in the docs means for Python 2, either: if values x and y both fit in an int, then so do ~x, x|y and x&y. We already assume in the Python source that the underlying representation is two's complement (no padding bits, no trap representation, etc.), so there aren't any complications from platforms where the C representation is ones' complement or sign-magnitude. ---------- nosy: +mark.dickinson _______________________________________ Python tracker <report@bugs.python.org> <http://bugs.python.org/issue29710> _______________________________________
Mark Dickinson added the comment:
It's not really clear what that line in the docs means for Python 2, either
Ah, I guess it still kinda sorta applies for the left-shift operator, though even then, Python has promoted the result to long for many versions now. So the only "overflow" that's really relevant on Python 2 is "overflow" from int to long in the case of left shift. ---------- _______________________________________ Python tracker <report@bugs.python.org> <http://bugs.python.org/issue29710> _______________________________________
Nick Coghlan added the comment: Added 2.7 to the list of affected versions. Clearly my 2's-complement arithmetic is incredibly rusty, as for some reason I was thinking "~(-sys.maxint-1)" could overflow, but no, the answer to that is just "sys.maxint" :) ---------- versions: +Python 2.7 _______________________________________ Python tracker <report@bugs.python.org> <http://bugs.python.org/issue29710> _______________________________________
Nick Coghlan added the comment: I think the simplest fix to make the docs "not wrong" would be to just delete the part in parentheses. Beyond that, I'm not quite sure how to concisely describe the actual behaviour, but I think the mention of "2's complement" isn't especially helpful in its current form, since we don't give a clear sense of how the translation from an arbitrary length integer to a suitable 2's complement form is handled. For `~n`, the most concise explanation is the arithmetic equivalent: it is always implemented as `-(n+1)` Similarly, for `x << n` and `x >> n`, they're now exactly equivalent to `x * 2 ** n` and `x // 2 ** n` without any overflow checking or internal representation qualification (as even in Python 2.x, left-shift will automatically promote to a long when needed) For `x | y` and `x & y`, things are a little more subtle, since that's where the internal 2's complement representation comes into play, but you can't just write out the formal definition of 2's complement at the Python level and get the same answer as is given by the binary operators:
-5 & 5 1 -5 | 5 -1
(~-5 + 1) & 5 # Effectively '5 & 5' 5 (~-5 + 1) | 5 # Effectively '5 | 5' 5
-5 | (~5+1) # Effectively '-5 & -5' -5 -5 & (~5+1) # Effectively '-5 | -5' -5
The problem here is that the sign bits of the operands matter a great deal, since they affect the sign expansion in the conversion to the 2's complement form, but that detail gets lost if the conversion is done prior to the bitwise binary operator invocation. One way to get the same results as the interpreter level algorithms is to use a 2's complement bit length of `1 + max(x.bit_length(), y.bit_length()`, so the equivalent operations become:
bin(0b1011 & 0b0101) # -5 & 5 -> 1 in 4 bit 2's complement '0b1' bin(0b1011 | 0b0101) # -5 | 5 -> -1 in 4 bit 2's complement '0b1111'
So perhaps a helpful change to make would be to move the note about negative numbers to a numbered footnote in the table, and state that the bitwise binary operations are semantically equivalent to calculations using two's complement in a bit-width of `1 + max(x.bit_length(), y.bit_length()`. ---------- _______________________________________ Python tracker <report@bugs.python.org> <http://bugs.python.org/issue29710> _______________________________________
Changes by Sanyam Khurana <sanyam.khurana01@gmail.com>: ---------- pull_requests: +1784 _______________________________________ Python tracker <report@bugs.python.org> <http://bugs.python.org/issue29710> _______________________________________
Mark Dickinson added the comment: So on re-reading the docs, I think we're misinterpreting this part:
this assumes that there are enough bits so that no overflow occurs during the operation
One way to think of | and & (and ~ and ^, too): 1. Find a positive integer n such that both x and y can be represented *without overflow* in n-bit two's complement. 2. Do the computation x | y (or x & y, x ^ y, ~x, as appropriate) in n-bit two's-complement arithmetic, giving an n-bit two's complement result that we re-interpret as a signed integer in the usual way. I think the "so that no overflow occurs" refers to choosing n sufficient large in the first step above. Note that it doesn't matter what value of n we choose to use, so long as it's large enough: evaluating 5 & -17 will work just as well using 8-bit two's complement as using 23-bit two's complement --- we'll get the same result either way. (I personally tend to find it easier to think in terms of the infinite 2-adic representation, which is essentially what you get by extending the 0 or 1 sign bit leftwards into an infinite string of 0s or 1s.) ---------- _______________________________________ Python tracker <report@bugs.python.org> <http://bugs.python.org/issue29710> _______________________________________
Mark Dickinson added the comment: Adding Tim Peters to the nosy, since I suspect (without actually having checked) that this is his language. ---------- nosy: +tim.peters _______________________________________ Python tracker <report@bugs.python.org> <http://bugs.python.org/issue29710> _______________________________________
Martin Panter <vadmium+py@gmail.com> added the comment: I find the model in terms of “bit_length” hard to understand. You have to understand what bit_length returns, and why you added 1. Bit_length is awkward for negative numbers. It only uses the absolute value, which would give off-by-one problems with negative values, so I guess you added 1 to compensate. I understand the bitwise operations as using two’s complement extended to an unlimited width, so that negative values have a series of ones for the most-significant bits. I presume this is what your “2-adic representation” is. Having this spelled out may have helped when I was learning Python. ---------- nosy: +martin.panter _______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue29710> _______________________________________
Nick Coghlan <ncoghlan@gmail.com> added the comment: Right, and that's why I think we're better off focusing on the arithmetic explanations wherever they apply. The problem is that for "x | y" and "x & y" there's no avoiding discussing the 2's complement representation. Martin, would you find the reference to `bit_length()` in the current PR easier to follow if it had a second follow-up sentence like the one below: === Bitwise binary operations are semantically equivalent to calculations using 2's complement in a bit-width of ``1 + max(x.bit_length(), y .bit_length()``. This choice of bit-width ensures there is sufficient space for the absolute value of both operands, while also providing space for an explicit sign bit (representing the conceptually infinite series of zeros or ones at the left of a 2's complement value). === That retains the precision of the currently suggested definition (for the benefit of language implementors), but also spells out the rationale for that definition (the "1 +" is for the sign bit, while the abs() is implicit in the fact that bit_length() assumes 2's complement and hence doesn't allow space for an explicit sign bit). ---------- _______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue29710> _______________________________________
Mark Dickinson <dickinsm@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@bugs.python.org> <https://bugs.python.org/issue29710> _______________________________________
Martin Panter <vadmium+py@gmail.com> added the comment: FWIW I find Mark’s suggestion pretty good: “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.” ---------- _______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue29710> _______________________________________
Nick Coghlan <ncoghlan@gmail.com> added the comment: I like Mark's phrasing as well. For precision, I'd still like to give an exact algorithmic formulation of what "large enough" means in this context, though. Something like: 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. ("Large enough" for this purpose is ``1 + max(x.bit_length(), y .bit_length()``, with the extra bit being needed to handle sign extension appropriately) ---------- _______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue29710> _______________________________________
Tim Peters <tim@python.org> added the comment: To answer the old accusation ;-), no, this isn't my wording. I _always_ explain that Python's integer bit operations act as if the integers were stored in 2's-complement representation but with an infinite number of sign bits. That's all. That provides insight. For example, then it's dead obvious that `-1 == ~0` (both an infinite solid string of 1 bits); that for any integer `i`, `-1 ^ i == ~i" (both flip each bit in `i`); and that for any positive integers `i` and `j` it's necessarily the case that `-i ^ -j` is positive (because the infinite strings of sign bits cancel out). The reference manual is under no obligation to explain how to _implement_ this illusion, and I don't think it's helpful to try. People here are struggling to explain how to pick a number of bits "big enough" to make it all work out on a case by case basis, but the single answer "infinity" is big enough to apply in all cases ;-) ---------- _______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue29710> _______________________________________
Nick Coghlan <ncoghlan@gmail.com> added the comment: I think we have a fairly different notion of what clarity means here - I have no mental concept whatsoever of how to do two's complement arithmetic with an infinite number of sign bits (I learned most of what I know about two's complement by working with fixed point 16-bit and 32-bit microprocessors), so the infinite bits explanation provides me with very little useful insight, whereas I can readily cope with the notion of storing a single extra sign extension bit beyond the minimum required to hold the operands' two's complement representations. That said, I do like the idea of using infinite precision arithmetic as the formal definition of the intended language semantics, which would lead to wording like the following: ================= Each bitwise operation has the same result as though carried out in two's complement with an infinite number of sign bits. In practice, performing the calculation with one extra sign extension bit (a bit-width of ``1 + max(x.bit_length(), y.bit_length()``) is sufficient to get the expected result. ================= ---------- _______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue29710> _______________________________________
Tim Peters <tim@python.org> added the comment: Nick, that seems a decent compromise. "Infinite string of sign bits" is how Guido & I both thought of it when the semantics of longs were first defined, and others in this report apparently find it natural enough too. It also applies to all 6 operations in the table as-is. It appears that a bit-width of ``1 + max(x.bit_length(), y.bit_length()`` only applies as-is to 3 (~ has only one operand, while the bit length of the RHS doesn't matter for << and >>). Provided that's clarified, I'd only suggest inserting "at least" before "one extra sign extension bit" and after "a bit-width of". That's a bridge between the "infinite" and "fixed-albeit-variable-width" views: "plus 1" is the smallest approximation to infinity that works, but anything at least that large works too. ---------- _______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue29710> _______________________________________
Nick Coghlan <ncoghlan@gmail.com> added the comment: The restriction of the footnote to ``x & y``, ``x | y``, and ``x ^ y`` was going to come from the fact that only those rows in the table will reference the new note. However, it likely makes sense to repeat the relevant expressions in the footnote as well, since that makes it clearer what ``x`` and ``y`` refer to in the second sentence. Latest proposal: ================= The results of ``x | y``, ``x ^ y``, and ``x & y`` are calculated as though carried out in two's complement with an infinite number of sign bits. In practice, performing the calculation with at least one extra sign extension bit (a working bit-width of ``1 + max(x.bit_length(), y.bit_length()`` or more) is sufficient to get the expected result. ================= ---------- _______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue29710> _______________________________________
Tim Peters <tim@python.org> added the comment: Well, all 6 operations "are calculated as though carried out in two's complement with an infinite number of sign bits", so I'd float that part out of the footnote and into the main text. When, e.g., you're thinking of ints _as_ bitstrings, it's essentially useless to think of `n >> 13` as being equivalent to `n // 2**13`. Quick: what's ~0 >> 13? Well, ~0 is an infinite string of 1 bits, so shifting it right by any finite number of bits doesn't change it. That, mathematically, floor(~0 / 8192) = -1 is only interesting if you're thinking of ~0 as being an integer instead. And, if you are, _then_ you need to know that the infinite string of 1 bits ~0 represents is viewed as being a 2's-complement representation of -1. But so long as you're sticking to the bitstring view, the "2's complement" part is irrelevant to anything these 6 operations do. Indeed, in the very earliest versions of Python, longs (but not ints!) were viewed as being 1's-complement infinite bitstrings, but "infinite string of sign bits" was just as applicable to what these operations did then. The meaning of what these operations compute _as bitstrings_ is independent of how bitstrings are mapped to and from integers. When longs changed from 1's-comp to 2's-comp only the latter changed; code using longs as bitstrings wasn't affected. So, in all, there's quite a bit of background these telegraphic docs are glossing over. You (Nick) don't seem to ever think of them as being bitstrings, but what the "bitwise operators" do was driven by the bitstring view. That some of them can also be defined by arithmetic (+ - * /) is secondary. It may well take more text to get that all across than is suitable here, though. ---------- _______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue29710> _______________________________________
Nick Coghlan <ncoghlan@gmail.com> added the comment: OK, that makes sense to me. Given that, there'd be two changes proposed. 1. Replace the opening paragraph of https://docs.python.org/3/library/stdtypes.html#bitwise-operations-on-intege... (the one I originally quoted when opening this issue) with the text: ===================== Bitwise operations only make sense for integers. The result of bitwise operations is calculated as though carried out in two's complement with an infinite number of sign bits. ===================== 2. Add a new footnote ``(4)`` to the table for the ``|``, ``^``, and ``&`` entries that reads: ===================== 4. Performing these calculations with at least one extra sign extension bit in the internal representation (a working bit-width of ``1 + max(x.bit_length(), y.bit_length()`` or more) is sufficient to get the same result as if there were an infinite number of sign bits. ===================== ---------- _______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue29710> _______________________________________
Mark Dickinson <dickinsm@gmail.com> added the comment: The wording for change 1 looks fine to me. For change 2, the mention of the internal representation is misleading, since the internal representation of (long) integers in current CPython is effectively sign-magnitude, and so there are some shenanigans to make the operations behave *as though* the internal representation were some form of two's complement [1]. The previously proposed wording (in msg321679) (with the "infinite sign bits" extracted into the main text as Tim suggests) looks fine to me. [1] https://github.com/python/cpython/blob/c9265c1534b7e62bb9b15460d0420c0c3bb57... ---------- _______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue29710> _______________________________________
Tim Peters <tim@python.org> added the comment: Ya, Mark's got a point there. Perhaps s/the internal/a finite two's complement/ ? ---------- _______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue29710> _______________________________________
Nick Coghlan <ncoghlan@gmail.com> added the comment: Ah, "the internal representation" was meant to refer a hypothetical representation, rather than literally to CPython's actual implementation, but now that you point it out, I agree my wording is ambiguous. I like Tim's suggested replacement: ===================== 4. Performing these calculations with at least one extra sign extension bit in a finite two's complement representation (a working bit-width of ``1 + max(x.bit_length(), y.bit_length()`` or more) is sufficient to get the same result as if there were an infinite number of sign bits. ===================== ---------- _______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue29710> _______________________________________
Mark Dickinson <dickinsm@gmail.com> added the comment:
4. Performing these calculations with at least one extra sign extension bit in a finite two's complement representation (a working bit-width of ``1 + max(x.bit_length(), y.bit_length()`` or more) is sufficient to get the same result as if there were an infinite number of sign bits.
LGTM ---------- _______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue29710> _______________________________________
Sanyam Khurana <sanyam.khurana01@gmail.com> added the comment: Seems good to me. I've made the changes in the PR. ---------- _______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue29710> _______________________________________
Tim Peters <tim@python.org> added the comment: @CuriousLearner, does the PR also include Nick's first suggested change? Here: """ 1. Replace the opening paragraph of https://docs.python.org/3/library/stdtypes.html#bitwise-operations-on-intege... (the one I originally quoted when opening this issue) with the text: ===================== Bitwise operations only make sense for integers. The result of bitwise operations is calculated as though carried out in two's complement with an infinite number of sign bits. ===================== """ ---------- _______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue29710> _______________________________________
Sanyam Khurana <sanyam.khurana01@gmail.com> added the comment: Hey Tim,
@CuriousLearner, does the PR also include Nick's first suggested change? Here:
""" ===================== Bitwise operations only make sense for integers. The result of bitwise operations is calculated as though carried out in two's complement with an infinite number of sign bits. ===================== """ I think it was then discussed to keep this line as: """ =========== Bitwise operations only make sense for integers. Negative numbers are treated as their 2's complement value. =========== """ Does this needs to be changed? Here is the link of the PR: https://github.com/python/cpython/pull/1691/files#diff-7498e907ba97646df434a... ---------- _______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue29710> _______________________________________
Tim Peters <tim@python.org> added the comment: Nick suggested two changes on 2018-07-15 (look above). Mark & I agreed about the first change, so it wasn't mentioned again after that. All the rest has been refining the second change. ---------- _______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue29710> _______________________________________
Sanyam Khurana <sanyam.khurana01@gmail.com> added the comment: On, yes, I think I missed the first point, earlier. Thank You! I did the changes. ---------- _______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue29710> _______________________________________
Nick Coghlan <ncoghlan@gmail.com> added the comment: New changeset b4bc5cab82e6855e4ebc33ba0b669ddffad30fb3 by Nick Coghlan (Sanyam Khurana) in branch 'master': bpo-29710: Clarify documentation for Bitwise binary operation (GH-1691) https://github.com/python/cpython/commit/b4bc5cab82e6855e4ebc33ba0b669ddffad... ---------- _______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue29710> _______________________________________
Change by miss-islington <mariatta.wijaya+miss-islington@gmail.com>: ---------- keywords: +patch pull_requests: +8025 stage: needs patch -> patch review _______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue29710> _______________________________________
Change by miss-islington <mariatta.wijaya+miss-islington@gmail.com>: ---------- pull_requests: +8026 _______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue29710> _______________________________________
Nick Coghlan <ncoghlan@gmail.com> added the comment: Mark & Tim: thanks for the discussion and clarifications above, I learned some new things myself! Sanyam: thanks for the patch, and for your patience while we figured out what we wanted the new wording to actually say :) (Technically the backport PRs are still in progress, but I'll track that through the GitHub notifications) ---------- resolution: -> fixed stage: patch review -> resolved status: open -> closed _______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue29710> _______________________________________
miss-islington <mariatta.wijaya+miss-islington@gmail.com> added the comment: New changeset 8764a6ffda896af4586f07b55d7df916f86dd9b0 by Miss Islington (bot) in branch '3.7': bpo-29710: Clarify documentation for Bitwise binary operation (GH-1691) https://github.com/python/cpython/commit/8764a6ffda896af4586f07b55d7df916f86... ---------- nosy: +miss-islington _______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue29710> _______________________________________
miss-islington <mariatta.wijaya+miss-islington@gmail.com> added the comment: New changeset 3100b7e710dccdcfbc6991ea7e8985a1881d42e6 by Miss Islington (bot) in branch '3.6': bpo-29710: Clarify documentation for Bitwise binary operation (GH-1691) https://github.com/python/cpython/commit/3100b7e710dccdcfbc6991ea7e8985a1881... ---------- _______________________________________ Python tracker <report@bugs.python.org> <https://bugs.python.org/issue29710> _______________________________________
participants (7)
-
Mark Dickinson -
Martin Panter
-
miss-islington
-
Nick Coghlan
-
Sanyam Khurana
-
Tim Peters
-
Wolfgang Maier