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

推荐学习书目

› 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 2051 days ago, the information mentioned may be changed or developed.

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

length

二进制

Python

函数

6 replies • 2021-02-13 04:22:19 +08:00

mogg

Feb 12, 2021

log n 啊……

mogg

Feb 12, 2021

对不起看错了，常规算法是 O(log x ) or O(n)
固定位数有优化到 O(log 32/64……)的算法（记得 csapp 上有）
Python 的具体实现得看看源码（

lxy42

Feb 12, 2021

正好在看 Python 源码, [int_bit_length_impl]( https://github.com/python/cpython/blob/master/Objects/longobject.c#L5256).

从源码来看是 O(1).

littleMaple

Feb 12, 2021

@lxy42 #3 感谢解惑！

littleMaple

Feb 12, 2021

@mogg #2 感谢回复！我这就去看 CSAPP，之前一直放着.

msg7086

Feb 13, 2021 via Android

本质上应该是 lzcnt 吧，让 CPU 算的话是常数时间。
徒手算的话应该也能优化到常数时间。