V2EX = way to explore V2EX 是一个关于分享和探索的地方
Sign Up Now For Existing Member Sign In
推荐学习书目 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 1900 days ago, the information mentioned may be changed or developed.
假设某整数 x 的二进制最高有效位位数为 n，那么 x.bit_length() 的时间复杂度是 O(n) 还是 O(1) 呢？
 | 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