Minimum bit length needed for a positive integer in Python

Question

1 = 0b1 -> 1
5 = 0b101 -> 3
10 = 0b1010 -> 4
100 = 0b1100100 -> 7
1000 = 0b1111101000 -> 10
…

How can I get the bit length of an integer, i.e. the number of bits that are necessary to represent a positive integer in Python?

Answer 1

In python 2.7+ there is a int.bit_length() method:

>>> a = 100
>>> a.bit_length()
7

Answer 2

>>> len(bin(1000))-2
10
>>> len(bin(100))-2
7
>>> len(bin(10))-2
4

Note: will not work for negative numbers, may be need to substract 3 instead of 2

Answer 3

If your Python version has it (≥2.7 for Python 2, ≥3.1 for Python 3), use the bit_length method from the standard library.

Otherwise, len(bin(n))-2 as suggested by YOU is fast (because it's implemented in Python). Note that this returns 1 for 0.

Otherwise, a simple method is to repeatedly divide by 2 (which is a straightforward bit shift), and count how long it takes to reach 0.

def bit_length(n): # return the bit size of a non-negative integer
    bits = 0
    while n >> bits: bits += 1
    return bits

It is significantly faster (at least for large numbers — a quick benchmarks says more than 10 times faster for 1000 digits) to shift by whole words at a time, then go back and work on the bits of the last word.

def bit_length(n): # return the bit size of a non-negative integer
    if n == 0: return 0
    bits = -32
    m = 0
    while n:
        m = n
        n >>= 32; bits += 32
    while m: m >>= 1; bits += 1
    return bits

In my quick benchmark, len(bin(n)) came out significantly faster than even the word-sized chunk version. Although bin(n) builds a string that's discarded immediately, it comes out on top due to having an inner loop that's compiled to machine code. (math.log is even faster, but that's not important since it's wrong.)

Answer 4

Here we can also use slicing.

For positive integers, we'd start from 2:

len(bin(1)[2:])
len(bin(5)[2:])
len(bin(10)[2:])
len(bin(100)[2:])
len(bin(1000)[2:])

which would print:

1
3
4
7
10

For negative integers, we'd start from 3:

len(bin(-1)[3:])
len(bin(-5)[3:])
len(bin(-10)[3:])
len(bin(-100)[3:])
len(bin(-1000)[3:])

which would print:

1
3
4
7
10

Answer 5

def bitcounter(n):
    return math.floor(math.log(n,2)) + 1

EDIT fixed so that it works with 1

Answer 6

Here is another way:

def number_of_bits(n):
    return len('{:b}'.format(n))

Not so efficient I suppose, but doesn't show up in any of the previous answers...

Answer 7

This solution takes advantage of .bit_length() if available, and falls back to len(hex(a)) for older versions of Python. It has the advantage over bin that it creates a smaller temporary string, so it uses less memory.

Please note that it returns 1 for 0, but that's easy to change.

_HEX_BIT_COUNT_MAP = {
    '0': 0, '1': 1, '2': 2, '3': 2, '4': 3, '5': 3, '6': 3, '7': 3}

def bit_count(a):
  """Returns the number of bits needed to represent abs(a). Returns 1 for 0."""
  if not isinstance(a, (int, long)):
    raise TypeError
  if not a:
    return 1
  # Example: hex(-0xabc) == '-0xabc'. 'L' is appended for longs.
  s = hex(a)
  d = len(s)
  if s[-1] == 'L':
    d -= 1
  if s[0] == '-':
    d -= 4
    c = s[3]
  else:
    d -= 3
    c = s[2]
  return _HEX_BIT_COUNT_MAP.get(c, 4) + (d << 2)


# Use int.bit_length and long.bit_length introduced in Python 2.7 and 3.x.
if getattr(0, 'bit_length', None):
  __doc = bit_count.__doc__
  def bit_count(a):
    return a.bit_length() or 1
  bit_count.__doc__ = __doc

assert bit_count(0) == 1
assert bit_count(1) == 1
assert bit_count(2) == 2
assert bit_count(3) == 2
assert bit_count(63) == 6
assert bit_count(64) == 7
assert bit_count(75) == 7
assert bit_count(2047) == 11
assert bit_count(2048) == 12
assert bit_count(-4007) == 12
assert bit_count(4095) == 12
assert bit_count(4096) == 13
assert bit_count(1 << 1203) == 1204
assert bit_count(-(1 << 1203)) == 1204
assert bit_count(1 << 1204) == 1205
assert bit_count(1 << 1205) == 1206
assert bit_count(1 << 1206) == 1207