假设某整数 x
的二进制最高有效位位数为 n
,那么 x.bit_length()
的时间复杂度是 O(n)
还是 O(1)
呢?
1
mogg 2021-02-12 20:08:40 +08:00
log n 啊……
|
2
mogg 2021-02-12 20:13:54 +08:00 1
对不起看错了,常规算法是 O(log x ) or O(n)
固定位数有优化到 O(log 32/64……)的算法(记得 csapp 上有) Python 的具体实现得看看源码( |
3
lxy42 2021-02-12 20:34:54 +08:00 1
正好在看 Python 源码, [int_bit_length_impl]( https://github.com/python/cpython/blob/master/Objects/longobject.c#L5256).
从源码来看是 O(1). |
4
littleMaple OP @lxy42 #3 感谢解惑!
|
5
littleMaple OP @mogg #2 感谢回复!我这就去看 CSAPP,之前一直放着.
|
6
msg7086 2021-02-13 04:22:19 +08:00 via Android 1
本质上应该是 lzcnt 吧,让 CPU 算的话是常数时间。
徒手算的话应该也能优化到常数时间。 |