Bit length of int or long?

[Simon Langley]

François Pinard wrote:

> I would have vaguely hoped that len(3) or len(3L) gives me the number of bits
> taken by the integer 3, but that function is not available over integers.

[snip]

> P.S. - Yet, how does one ideally proceed to know the bit length of an
> integer?  I presume `math.frexp' is not too slow at producing the first
> float.  Floats are a bit unexpected in my little integer-only application.

I've been using this.  My ints are all longs and might be v. long

firstShift = 2**7                                             # assume bit size ~
128 bits.  If much more use a bigger power of 2 here
lotsof1s = (1L << firstShift) - 1L

def  bitsize(x):                                                # Number of
significant bits of an int/long
   if x == 0: return 0
   if x < 0: x = -x
   shift, toobig, s = firstShift, lotsof1s, 0          # initially shift out
'shift' bits at a time
   while toobig > 0:
      while x >= toobig:                                    # x has at least as
many bits as toobig
           x, s = x >> shift, s + shift                    # shift it and count
bits
       if x == 0: return s
       shift = shift >> 1                                      # half the number
of bits tested
       toobig = toobig >> shift                           # and loose half the
bits
  return s

This removes bits first 128 at a time, when the bit size is < 128 it trys 64, 32,
...

I would recommend Guido's for smaller numbers: this was strictly for v. big
numbers

Simon
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Simon Langley
Email: Simon.Langley at uwe.ac.uk
University of the West of England
Bristol BS16 1QY
England