[New-bugs-announce] [issue46488] listsort.txt wrongly assumes you cannot calculate leading zeros in O(1) time.
report at bugs.python.org
Sun Jan 23 12:08:12 EST 2022
New submission from Barry Schwartz <github at crudfactory.com>:
The Objects/listsort.txt incorrectly implies that it is not possible to compute leading zero bits in O(1) time, using only standard C. For a fixed integer size it can be done, for instance, using de Bruijn sequences. See https://www.chessprogramming.org/BitScan
(The existence of such methods is not as widely known as it ought to be.)
assignee: docs at python
nosy: chemoelectric, docs at python
title: listsort.txt wrongly assumes you cannot calculate leading zeros in O(1) time.
versions: Python 3.11
Python tracker <report at bugs.python.org>
More information about the New-bugs-announce