Python 的 int.bit_length() 函数的时间复杂度是多少呢？
資深大佬 : littleMaple 2
假设某整数 x 的二进制最高有效位位数为 n，那么 x.bit_length() 的时间复杂度是 O(n) 还是 O(1) 呢？
大佬有話說 (6)
Python 的 int.bit_length() 函数的时间复杂度是多少呢？
-
資深大佬 : mogglog 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 算的话是常数时间。
徒手算的话应该也能优化到常数时间。 -