[New-bugs-announce] [issue46488] listsort.txt wrongly assumes you cannot calculate leading zeros in O(1) time.

[Barry Schwartz]

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
components: Documentation
messages: 411384
nosy: chemoelectric, docs at python
priority: normal
severity: normal
status: open
title: listsort.txt wrongly assumes you cannot calculate leading zeros in O(1) time.
type: performance
versions: Python 3.11

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue46488>
_______________________________________