Bit length of int or long?

Greg Ewing greg at cosc.canterbury.ac.nz
Wed May 17 21:44:07 EDT 2000


François Pinard wrote:
> 
> Sounds rather slow, especially for big numbers.

Here's one that should be O(log n) where n is the
number of bits:

def bitlen(x):
  """Number of bits to represent integer x."""
  n = 0
  b = 1
  while (x >> n) > 0:
    n = n + b
    b = b * 2
  while b > 0:
    b = b / 2
    if (x >> (n - b)) == 0:
      n = n - b
  return n

# Test

if __name__ == "__main__":
  for x in xrange(32):
    print "%5d%5d" % (x, bitlen(x))
  x = 1234567890123456789L
  print x, bitlen(x)

-- 
Greg Ewing, Computer Science Dept,
+--------------------------------------+
University of Canterbury,	   | A citizen of NewZealandCorp, a	  |
Christchurch, New Zealand	   | wholly-owned subsidiary of USA Inc.  |
greg at cosc.canterbury.ac.nz	   +--------------------------------------+



More information about the Python-list mailing list