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