Positive integer bit length 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 needed to represent a positive integer in Python?

Answer 1

 import math def number_of_bits(n): return int(math.log(n, 2)) + 1 

Answer 2

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

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

Answer 3

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

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

Answer 4

If your version of Python has (≥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 , quickly (because it is implemented in Python). Note that this returns 1 for 0.

Otherwise, a simple method is to divide by 2 (which is a direct bit shift) and calculate 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 

This is much faster (at least for large numbers - quick tests say more than 10 times faster by 1000 digits) shift in whole words at a time, and 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 test, len(bin(n)) came out significantly faster than even a version with a word size of size. Although bin(n) builds a line that is immediately discarded, it appears on top because there is an inner loop compiled for machine code. ( math.log even faster, but it doesn’t matter, as it’s wrong.)

Answer 5

Here is another way:

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

Not as effective, I suppose, but does not appear in any of the previous answers ...

Answer 6

Just store the value in a variable and access it bit_length() . Available in both Python 2 and 3.

 n = 5 print(n.bit_length()) 

Answer 7

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

EDIT fixed so that it works with 1

Answer 8

This solution uses .bit_length() , if available, and reverts to len(hex(a)) for older versions of Python. The advantage over bin is that it creates a smaller temporary string, so it uses less memory.

Note that it returns 1 for 0, but this is 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