classification
Title: Specification of bitshift on integers should clearly state floor division used
Type: enhancement Stage: patch review
Components: Documentation Versions: Python 3.10, Python 3.9, Python 3.8, Python 3.7
process
Status: open Resolution:
Dependencies: Superseder:
Assigned To: docs@python Nosy List: ZackerySpytz, docs@python, mark.dickinson, miss-islington, ncoghlan
Priority: normal Keywords: patch

Created on 2020-01-11 06:59 by ncoghlan, last changed 2020-05-26 08:38 by mark.dickinson.

Pull Requests
URL Status Linked Edit
PR 20347 merged ZackerySpytz, 2020-05-24 05:54
PR 20414 merged miss-islington, 2020-05-26 08:16
PR 20415 merged miss-islington, 2020-05-26 08:16
PR 20416 merged miss-islington, 2020-05-26 08:17
PR 20417 closed miss-islington, 2020-05-26 08:17
Messages (9)
msg359786 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2020-01-11 06:59
While reviewing ISO-IECJTC1-SC22-WG23's latest draft of their Python security annex, I noticed that https://docs.python.org/3.7/library/stdtypes.html#bitwise-operations-on-integer-types doesn't explicitly state that *floor* division is used for right shift operations, so right-shifting a negative number by more bits than it contains gives -1 rather than 0.

This is consistent with the way the language spec defines both binary right-shifts (as division by "pow(2, n)" and floor division (as rounding towards negative infinity), so this is just a documentation issue to note that we should make it clearer that this behaviour is intentional.
msg359817 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2020-01-11 19:10
Is the fix as simple as adding the word "floor" before "division" in the "equivalent to division by [...]" phrase?

> A right shift by n bits is equivalent to floor division by pow(2, n) without overflow check. 

This text was probably written before // was introduced; maybe we can rewrite in terms of //? "x >> n" should be identical to "x // pow(2, n)" for any nonnegative "n".

I confess that I've no idea what the "without overflow check" bit means, but I suspect it's no longer relevant post int/long-unification.
msg359832 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2020-01-12 05:12
Aye, adding "floor" to the existing footnote would be the minimal fix. I'm just wondering whether it's also worth stating that this means that positive integers saturate at zero, while negative integers saturate at -1.
msg369777 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2020-05-24 10:17
> I confess that I've no idea what the "without overflow check" bit means

After some digging, it is indeed to do with the int/long unification:

- In Python 2.1, arithmetic operations on ints would raise OverflowError on overflow.
- Except that left shift did not raise: shifted out bits were simply lost.  This is described in PEP 237.

In Python 2.2, arithmetic operations (including left shift) were changed to produce a long instead of overflowing.

The "without overflow check" part of the doc almost certainly refers to the Python 2.1 behaviour (at least for left shift; I'm guessing that for right shift, where overflow isn't possible, this was just a redundant copy-paste), and was never updated. It should be removed for both left shift and right shift.
msg369952 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2020-05-26 08:16
New changeset af7553ac95a96713be847dd45bc5a8aeb0a75955 by Zackery Spytz in branch 'master':
bpo-39301: State that floor division is used for right shift operations (GH-20347)
https://github.com/python/cpython/commit/af7553ac95a96713be847dd45bc5a8aeb0a75955
msg369954 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2020-05-26 08:33
New changeset cc0f50d62c75a1d171f5de9b56caef64e79eb013 by Miss Islington (bot) in branch '3.9':
bpo-39301: State that floor division is used for right shift operations (GH-20347) (GH-20414)
https://github.com/python/cpython/commit/cc0f50d62c75a1d171f5de9b56caef64e79eb013
msg369955 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2020-05-26 08:33
New changeset c2a177adf3575d4eb81030fba851f78d7a8e3f51 by Miss Islington (bot) in branch '3.8':
bpo-39301: State that floor division is used for right shift operations (GH-20347) (GH-20415)
https://github.com/python/cpython/commit/c2a177adf3575d4eb81030fba851f78d7a8e3f51
msg369956 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2020-05-26 08:34
New changeset b068d892c1ba7b996e43aceb974bfadac3c577ed by Miss Islington (bot) in branch '3.7':
bpo-39301: State that floor division is used for right shift operations (GH-20347) (GH-20416)
https://github.com/python/cpython/commit/b068d892c1ba7b996e43aceb974bfadac3c577ed
msg369957 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2020-05-26 08:38
Thanks Zackery for the fix! Nick: is this good enough to close, or would you like to see something more here?
History
Date User Action Args
2020-05-26 08:38:39mark.dickinsonsetmessages: + msg369957
2020-05-26 08:34:07mark.dickinsonsetmessages: + msg369956
2020-05-26 08:33:46mark.dickinsonsetmessages: + msg369955
2020-05-26 08:33:13mark.dickinsonsetmessages: + msg369954
2020-05-26 08:17:14miss-islingtonsetpull_requests: + pull_request19676
2020-05-26 08:17:05miss-islingtonsetpull_requests: + pull_request19675
2020-05-26 08:16:56miss-islingtonsetpull_requests: + pull_request19674
2020-05-26 08:16:47miss-islingtonsetnosy: + miss-islington
pull_requests: + pull_request19673
2020-05-26 08:16:41mark.dickinsonsetmessages: + msg369952
2020-05-25 08:18:12mark.dickinsonsetversions: + Python 3.10
2020-05-24 10:17:45mark.dickinsonsetmessages: + msg369777
2020-05-24 05:54:08ZackerySpytzsetkeywords: + patch
nosy: + ZackerySpytz

pull_requests: + pull_request19610
stage: needs patch -> patch review
2020-01-12 05:12:25ncoghlansetmessages: + msg359832
2020-01-11 19:10:47mark.dickinsonsetmessages: + msg359817
2020-01-11 18:37:42mark.dickinsonsetnosy: + mark.dickinson
2020-01-11 06:59:44ncoghlancreate