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

[littleMaple]

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

[mogg]

log n 啊……

[mogg]

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

[lxy42]

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

从源码来看是 O(1).

[littleMaple]

@lxy42 #3 感谢解惑！

[littleMaple]

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

[msg7086]

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