[issue15391] Add bitlength function to the math module

anon report at bugs.python.org
Thu Jul 19 01:32:23 CEST 2012


New submission from anon <UnluckyKitten at mailinator.com>:

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.

----------
components: Library (Lib)
messages: 165818
nosy: anon
priority: normal
severity: normal
status: open
title: Add bitlength function to the math module
type: enhancement

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue15391>
_______________________________________


More information about the Python-bugs-list mailing list