V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
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
littleMaple
V2EX  ›  Python

Python 的 int.bit_length() 函数的时间复杂度是多少呢?

  •  
  •   littleMaple ·
    MapleCCC · 2021-02-12 20:02:47 +08:00 · 2017 次点击
    这是一个创建于 1384 天前的主题,其中的信息可能已经有所发展或是发生改变。

    假设某整数 x 的二进制最高有效位位数为 n,那么 x.bit_length() 的时间复杂度是 O(n) 还是 O(1) 呢?

    6 条回复    2021-02-13 04:22:19 +08:00
    mogg
        1
    mogg  
       2021-02-12 20:08:40 +08:00
    log n 啊……
    mogg
        2
    mogg  
       2021-02-12 20:13:54 +08:00   ❤️ 1
    对不起看错了,常规算法是 O(log x ) or O(n)
    固定位数有优化到 O(log 32/64……)的算法(记得 csapp 上有)
    Python 的具体实现得看看源码(
    lxy42
        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).
    littleMaple
        4
    littleMaple  
    OP
       2021-02-12 21:24:56 +08:00
    @lxy42 #3 感谢解惑!
    littleMaple
        5
    littleMaple  
    OP
       2021-02-12 21:25:18 +08:00
    @mogg #2 感谢回复!我这就去看 CSAPP,之前一直放着.
    msg7086
        6
    msg7086  
       2021-02-13 04:22:19 +08:00 via Android   ❤️ 1
    本质上应该是 lzcnt 吧,让 CPU 算的话是常数时间。
    徒手算的话应该也能优化到常数时间。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3439 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 10:53 · PVG 18:53 · LAX 02:53 · JFK 05:53
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.