English 中文(简体)
Minimum bit length needed for a positive integer in Python
原标题:
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?

问题回答

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

>>> a = 100
>>> a.bit_length()
7
>>> 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

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.)

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
def bitcounter(n):
    return math.floor(math.log(n,2)) + 1

EDIT fixed so that it works with 1

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...

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




相关问题
Can Django models use MySQL functions?

Is there a way to force Django models to pass a field to a MySQL function every time the model data is read or loaded? To clarify what I mean in SQL, I want the Django model to produce something like ...

An enterprise scheduler for python (like quartz)

I am looking for an enterprise tasks scheduler for python, like quartz is for Java. Requirements: Persistent: if the process restarts or the machine restarts, then all the jobs must stay there and ...

How to remove unique, then duplicate dictionaries in a list?

Given the following list that contains some duplicate and some unique dictionaries, what is the best method to remove unique dictionaries first, then reduce the duplicate dictionaries to single ...

What is suggested seed value to use with random.seed()?

Simple enough question: I m using python random module to generate random integers. I want to know what is the suggested value to use with the random.seed() function? Currently I am letting this ...

How can I make the PyDev editor selectively ignore errors?

I m using PyDev under Eclipse to write some Jython code. I ve got numerous instances where I need to do something like this: import com.work.project.component.client.Interface.ISubInterface as ...

How do I profile `paster serve` s startup time?

Python s paster serve app.ini is taking longer than I would like to be ready for the first request. I know how to profile requests with middleware, but how do I profile the initialization time? I ...

Pragmatically adding give-aways/freebies to an online store

Our business currently has an online store and recently we ve been offering free specials to our customers. Right now, we simply display the special and give the buyer a notice stating we will add the ...

Converting Dictionary to List? [duplicate]

I m trying to convert a Python dictionary into a Python list, in order to perform some calculations. #My dictionary dict = {} dict[ Capital ]="London" dict[ Food ]="Fish&Chips" dict[ 2012 ]="...

热门标签