classification
Title: Add bitlength function to the math module enhancement Library (Lib)
process
Status: Resolution: closed not a bug alex, anon, jcea, mark.dickinson normal

Created on 2012-07-18 23:32 by anon, last changed 2012-07-20 11:51 by mark.dickinson. This issue is now closed.

Messages (4)
msg165818 - (view) Author: anon (anon) Date: 2012-07-18 23:32
```Many numeric algorithms require knowing the number of bits an integer has (for instance integer squareroots). For example this simple algorithm using shifts is O(n^2):

def bitl(x):
x = abs(x)
n = 0
while x > 0:
n = n+1
x = x>>1
return n

A simple O(n) algorithm exists:

def bitl(x):
if x==0: return 0
return len(bin(abs(x)))-2

It should be possible find the bit-length of an integer in O(1) however. O(n) algorithms with high constants simply don't cut it for many applications.

That's why I would propose adding an inbuilt function bitlength(n) to the math module. bitlength(n) would be the integer satisfying

bitlength(n) = ceil(log2(abs(n)+1))

Python more than ever with PyPy progressing is becoming a great platform for mathematical computation. This is an important building block for a huge number of algorithms but currently has no elegant or efficient solution in plain Python.```
msg165819 - (view) Author: Alex Gaynor (alex) * Date: 2012-07-18 23:34
`I think what you're looking for already exists: http://docs.python.org/dev/library/stdtypes.html#int.bit_length`
msg165821 - (view) Author: Jesús Cea Avión (jcea) * Date: 2012-07-19 00:17
```Closing as Invalid. I think that Alex is right.

Anon, if you think this is a mistake, please reopen and argument.```
msg165914 - (view) Author: Mark Dickinson (mark.dickinson) * Date: 2012-07-20 11:51
`Indeed, int.bit_length is the way to do this.`
History
Date User Action Args
2012-07-20 11:51:13mark.dickinsonsetnosy: + mark.dickinson
messages: + msg165914
2012-07-19 00:17:45jceasetstatus: open -> closed
resolution: not a bug
messages: + msg165821
2012-07-19 00:13:19jceasetnosy: + jcea
2012-07-18 23:34:58alexsetnosy: + alex
messages: + msg165819
2012-07-18 23:32:22anoncreate