假设某整数 x 的二进制最高有效位位数为 n，那么 x.bit_length() 的时间复杂度是 O(n) 还是 O(1) 呢？
推荐学习书目
› Learn Python the Hard Way
Python Sites
› PyPI - Python Package Index
› http://diveintopython.org/toc/index.html
› Pocoo
值得关注的项目
› PyPy
› Celery
› Jinja2
› Read the Docs
› gevent
› pyenv
› virtualenv
› Stackless Python
› Beautiful Soup
› 结巴中文分词
› Green Unicorn
› Sentry
› Shovel
› Pyflakes
› pytest
Python 编程
› pep8 Checker
Styles
› PEP 8
› Google Python Style Guide
› Code Style from The Hitchhiker's Guide
This topic created in 1949 days ago, the information mentioned may be changed or developed.
 |
1
mogg Feb 12, 2021
log n 啊……
|
|
2
mogg Feb 12, 2021  1
对不起看错了，常规算法是 O(log x ) or O(n)
固定位数有优化到 O(log 32/64……)的算法（记得 csapp 上有） Python 的具体实现得看看源码（ |
 |
3
lxy42 Feb 12, 2021 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 Feb 13, 2021 via Android 1
本质上应该是 lzcnt 吧，让 CPU 算的话是常数时间。
徒手算的话应该也能优化到常数时间。 |
Select Language