Add bitlength function to the math module

[anon]

BPO	15391
Nosy	@jcea, @mdickinson, @alex

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2012-07-19.00:17:45.583>
created_at = <Date 2012-07-18.23:32:22.303>
labels = ['invalid', 'type-feature', 'library']
title = 'Add bitlength function to the math module'
updated_at = <Date 2012-07-20.11:51:13.119>
user = 'https://bugs.python.org/anon'

bugs.python.org fields:

activity = <Date 2012-07-20.11:51:13.119>
actor = 'mark.dickinson'
assignee = 'none'
closed = True
closed_date = <Date 2012-07-19.00:17:45.583>
closer = 'jcea'
components = ['Library (Lib)']
creation = <Date 2012-07-18.23:32:22.303>
creator = 'anon'
dependencies = []
files = []
hgrepos = []
issue_num = 15391
keywords = []
message_count = 4.0
messages = ['165818', '165819', '165821', '165914']
nosy_count = 4.0
nosy_names = ['jcea', 'mark.dickinson', 'alex', 'anon']
pr_nums = []
priority = 'normal'
resolution = 'not a bug'
stage = None
status = 'closed'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue15391'
versions = []

[anon]

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.

[alex]

I think what you're looking for already exists: http://docs.python.org/dev/library/stdtypes.html#int.bit_length

[jcea]

Closing as Invalid. I think that Alex is right.

Anon, if you think this is a mistake, please reopen and argument.

[mdickinson]

Indeed, int.bit_length is the way to do this.