Number of bits/sizeof int

[Jon Clements]

Hi Group,

This has a certain amount of irony (as this is what I'm pretty much
after):-
From http://docs.python.org/dev/3.0/whatsnew/3.1.html:
"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.

Cheers,

Jon.

 

[John Machin]

Hi Group,

This has a certain amount of irony (as this is what I'm pretty much
after):-
Fromhttp://docs.python.org/dev/3.0/whatsnew/3.1.html:
"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.

For a positive integer, the simplest method (not necessarily the
fastest) is to count how many times you need to shift it right to make
it become zero.
For non-positive integers, what answers do you want?

 

[Gabriel Genellina]

This has a certain amount of irony (as this is what I'm pretty much
after):-
"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.

I'm sure *everyone* will now post his favourite algorithm... If you search
the archives, you'll find *tons* of versions. Ok, my take:

def number_of_bits(num):
assert num>=0
nbits = 1
max = 2
while max<=num:
nbits += 1
max += max
return nbits

 

[Jon Clements]

For a positive integer, the simplest method (not necessarily the
fastest) is to count how many times you need to shift it right to make
it become zero.
For non-positive integers, what answers do you want?

Thankfully, all integers are positive!

Must have been having a blonde moment, 'cos as soon as I read your
answer it was "of course that works". Not concerned about 'fast' as I
hardly think with DB and disk I/O I'm going to worry about bit-
shifting...

Much appreciated John,

Jon.

 

[Mark Wooding]

"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]

 

[Mark Dickinson]

Any tips on how to get this in 2.5.2 as that's the production version
I'm stuck with.

It's a bit cheeky, but:

from decimal import _nbits as nbits

should also work in 2.5.2 (but not in 2.5.1)!

Mark

 

[John Machin]

def nbits(x):

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

3 can be represented in 2 bits and at the same time -3 can be
represented in 2 bits?? But 2 bits can support only 2 ** 2 == 4
different possibilities, and -3 .. 3 is 7 different integers.

  ## Find upper bound of the form 2^(2^n) >= x.

Possibly you mean 2 ** ( 2 ** n) >= x

 

[casevh]

Hi Group,

This has a certain amount of irony (as this is what I'm pretty much
after):-
Fromhttp://docs.python.org/dev/3.0/whatsnew/3.1.html:
"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.

Cheers,

Jon.

If performance does become an issue, the newly released gmpy 1.04
includes bit_length().

casevh