Number of bits/sizeof int

[Mark Wooding]

Jon Clements <joncle at googlemail.com> writes:

> "The int() type gained a bit_length method that returns the number of
> bits necessary to represent its argument in binary:"
>
> Any tips on how to get this in 2.5.2 as that's the production version
> I'm stuck with.

def nbits(x):

  ## Special cases.
  if x == 0: return 0
  elif x < 0: x = -x

  ## Find upper bound of the form 2^(2^n) >= x.
  n = 1
  while True:
    y = x >> n
    if y == 0: break
    x = y
    n <<= 1

  ## Now binary search until we're done.
  a = n
  while n > 0:
    n >>= 1
    y = x >> n
    if y > 0:
      x = y
      a += n

  return a


-- [mdw]