how to get the thighest bit position in big integers?
mmga...@gmx.de
I'm using python to develop some proof-of-concept code for a
cryptographic application. My code makes extended use of python's
native bignum capabilities.
In many cryptographic applications there is the need for a function
'get_highest_bit_num' that returns the position number of the highest
set bit of a given integer. For example:
get_highest_bit_num( (1 << 159)) == 159
get_highest_bit_num( (1 << 160) - 1) == 159
get_highest_bit_num( (1 << 160)) == 160
I implemented this the following way:
def get_highest_bit_num(r):
i = -1
while r > 0:
r >>= 1
i = i + 1
return i
This works, but it is a very unsatisfying solution, because it is so
slow.
My second try was using the math.log function:
import math
r = (1 << 160) - 1
print highest_bit_num(r) # prints out 159
print math.floor(math.log(r, 2)) # prints out 160.0
We see that math.log can only serve as a heuristic for the highest bit
position. For small r, for example r = (1 << 16) - 1, the result from
math.log(, 2) is correct, for big r it isn't any more.
My question to the group: Does anyone know of a non-hackish way to
determine the required bit position in python? I know that my two
ideas
can be combined to get something working. But is there a *better* way,
that isn't that hackish?
cheers,
mmg
Gary Herron
> Hi,
>
> I'm using python to develop some proof-of-concept code for a
> cryptographic application. My code makes extended use of python's
> native bignum capabilities.
>
> In many cryptographic applications there is the need for a function
> 'get_highest_bit_num' that returns the position number of the highest
> set bit of a given integer. For example:
>
> get_highest_bit_num( (1 << 159)) == 159
> get_highest_bit_num( (1 << 160) - 1) == 159
> get_highest_bit_num( (1 << 160)) == 160
>
How about a binary search?
>>> from bisect import bisect
>>> BITS = [1<<n for n in range(1,1000)] # Use max number of bits here.
>>> bisect(BITS, 1<<159)
159
>>> bisect(BITS, 1<<160-1)
159
>>> bisect(BITS, 1<<160)
160
>>>
I have no clue if this is faster or not. The comparison function used
in the search is (potentially) slow, but the search is O(log n) on the
number of bits rather than O(n), so its worth a test.
If you run timing test, let us know the results.
Gary Herron
> I implemented this the following way:
>
> def get_highest_bit_num(r):
> i = -1
> while r > 0:
> r >>= 1
> i = i + 1
> return i
>
> This works, but it is a very unsatisfying solution, because it is so
> slow.
>
> My second try was using the math.log function:
>
> import math
> r = (1 << 160) - 1
> print highest_bit_num(r) # prints out 159
> print math.floor(math.log(r, 2)) # prints out 160.0
>
> We see that math.log can only serve as a heuristic for the highest bit
> position. For small r, for example r = (1 << 16) - 1, the result from
> math.log(, 2) is correct, for big r it isn't any more.
>
> My question to the group: Does anyone know of a non-hackish way to
> determine the required bit position in python? I know that my two
> ideas
> can be combined to get something working. But is there a *better* way,
> that isn't that hackish?
>
> cheers,
> mmg
Duncan Booth
> My question to the group: Does anyone know of a non-hackish way to
> determine the required bit position in python? I know that my two
> ideas
> can be combined to get something working. But is there a *better* way,
> that isn't that hackish?
>
How about using the hex representation of the value?
OFFSET = dict(("%x"%i, int(c)) for i,c in enumerate("5433222211111111"))
def get_highest_bit_num(r):
s = "%x"%r
return len(s) * 4 - OFFSET[s[0]]
Scott David Daniels
> I'm using python to develop some proof-of-concept code for a
> cryptographic application. My code makes extended use of python's
> native bignum capabilities.
>
> In many cryptographic applications there is the need for a function
> 'get_highest_bit_num' that returns the position number of the highest
> set bit of a given integer. For example:
> get_highest_bit_num( (1 << 159)) == 159
> def get_highest_bit_num(r):
> i = -1
> r >>= 1
> i += 1
> return i
> My second try was using the math.log function:
Since floating point has to identify the position of the highest bit,
you can use that hardware to "quickly" get to the highest bit. IEEE
has the mantissa .5 <= mantissa < 1., but some other floating point
formats treated the mantissa in different ranges. This should work
for anything where the exponent is truly a "binary point." In an older
IBM floating point format, for example, the exponent was a "hexadecimal
point," so the exponent only went up 1 when you multiplied by 16.
EXP_OF_ONE = math.frexp(1.0)[1]
def high_bit(value):
'''Find the highest order bit of a positive integer <= maxfloat'''
assert value > 0
return math.frexp(value)[1] - EXP_OF_ONE
--Scott David Daniels
Scott....@Acm.Org
Terry Reedy
> Hi,
>
> I'm using python to develop some proof-of-concept code for a
> cryptographic application. My code makes extended use of python's
> native bignum capabilities.
>
> In many cryptographic applications there is the need for a function
> 'get_highest_bit_num' that returns the position number of the highest
> set bit of a given integer. For example:
>
> get_highest_bit_num( (1 << 159)) == 159
> get_highest_bit_num( (1 << 160) - 1) == 159
> get_highest_bit_num( (1 << 160)) == 160
>
> I implemented this the following way:
>
> def get_highest_bit_num(r):
> i = -1
> while r > 0:
> r >>= 1
> i = i + 1
> return i
>
> This works, but it is a very unsatisfying solution, because it is so
> slow.
One alternative is to compare r against successive larger powers of 2,
starting with 2**0 == 1. Given that you have p=2**(n-1), you could test
whether generating 2**n for large n is faster as 1<<n or p<<1. A
refinement would be to raise the test power k at a time instead of 1 at
a time, tuning k for the implementation. Then do binary search in the
interval n, n+k. I once read that longs store 15 bits in pairs of
bytes. If true today, k = 15 might be a good choice since <<15 would
mean tacking on a pair of 0 bytes.
> My second try was using the math.log function:
>
> import math
> r = (1 << 160) - 1
> print highest_bit_num(r) # prints out 159
> print math.floor(math.log(r, 2)) # prints out 160.0
>
> We see that math.log can only serve as a heuristic for the highest bit
> position. For small r, for example r = (1 << 16) - 1, the result from
> math.log(, 2) is correct, for big r it isn't any more.
I tested and floor(log(2**n,2) == n for n in range(400), so your only
worry is that the answer is 1 too high. Easy to check and fix
res = int(math.floor(math.log(r, 2)))
if (1<<res) > r: res -=1
This works for 2**n-1 over the same range (all tests with 3.0rc1).
> My question to the group: Does anyone know of a non-hackish way to
> determine the required bit position in python?
If you call the standard methods hackish, I have no idea what would
satisfy you ;-)
Terry Jan Reedy
Aaron "Castironpi" Brady
> http://mail.python.org/mailman/listinfo/python-list
>
You can replace the dict if it's faster.
OFFSET= tuple( int(x) for x in "5433222211111111" )
def get_highest_bit_num(r):
s = "%x"%r
return len(s) * 4 - OFFSET[int(s[0],16)]
P.S. Back home, this sort of 'nitpicking' would be judged
unconstructive. Worth pointing out, or not worth saying?
P.S.S. 'Thighest' bit? I thought the spam filters would catch that.
Duncan Booth
>> OFFSET = dict(("%x"%i, int(c)) for i,c in enumerate("5433222211111111"))
>> def get_highest_bit_num(r):
>> s = "%x"%r
>> return len(s) * 4 - OFFSET[s[0]]
>
> You can replace the dict if it's faster.
>
> OFFSET= tuple( int(x) for x in "5433222211111111" )
> def get_highest_bit_num(r):
> s = "%x"%r
> return len(s) * 4 - OFFSET[int(s[0],16)]
>
> P.S. Back home, this sort of 'nitpicking' would be judged
> unconstructive. Worth pointing out, or not worth saying?
>
You could have answered your own question fairly quickly using the 'timeit'
module. In this case you trade off the dict lookup for a global name lookup
and a function call so I'd expect you would have made it slower and indeed
it seems to be about 30-40% slower than mine.
The math.floor/math.log version isn't so good for small values, but both
string versions seem to slow down dramatically somewhere around 526 bits
(2.8uS suddenly jumps to about 4us while the math version stays roughly
steady around 3.2uS).
Terry Reedy
> Since floating point has to identify the position of the highest bit,
> you can use that hardware to "quickly" get to the highest bit. IEEE
> has the mantissa .5 <= mantissa < 1., but some other floating point
> formats treated the mantissa in different ranges. This should work
> for anything where the exponent is truly a "binary point." In an older
> IBM floating point format, for example, the exponent was a "hexadecimal
> point," so the exponent only went up 1 when you multiplied by 16.
>
> EXP_OF_ONE = math.frexp(1.0)[1]
>
> def high_bit(value):
> '''Find the highest order bit of a positive integer <= maxfloat'''
> assert value > 0
> return math.frexp(value)[1] - EXP_OF_ONE
Your point, that taking floor(log2(x)) is redundant, is a good catch.
However, you should have added 'untested' ;-). When value has more
significant bits than the fp mantissa can hold, this expression can be 1
off (but no more, I assume). The following correction should be
sufficient:
res = math.frexp(value)[1] - EXP_OF_ONE
test = 1<<res
if test > r: res -= 1
elif 2*test < r: res += 1
For value = 2**n -1, n > 53, it is always 1 too high on my Intel
machine, so the first correction is sometimes needed. I do not know if
the second is or not.
Terry Jan Reedy
Scott David Daniels
> ...
> Your point, that taking floor(log2(x)) is redundant, is a good catch.
> However, you should have added 'untested' ;-). When value has more
> significant bits than the fp mantissa can hold, this expression can be 1
> off (but no more, I assume). The following correction should be
> sufficient:
>
> res = math.frexp(value)[1] - EXP_OF_ONE
> test = 1<<res
> if test > r: res -= 1
> elif 2*test < r: res += 1
Well, I did test, but poorly.
>>> high_bit(1<<587)
587
>>> high_bit(1<<587-1)
586
And of course, I _should_ have tested
>>> high_bit((1<<587)-1)
587
By the way, I wrote my response before any replies had happened; it was
not a correction to your post.
--Scott David Daniels
Scott....@Acm.Org
Rich Healey
Hash: SHA1
Aaron "Castironpi" Brady wrote:
>> --
>> http://mail.python.org/mailman/listinfo/python-list
>>
>
> You can replace the dict if it's faster.
>
> OFFSET= tuple( int(x) for x in "5433222211111111" )
> def get_highest_bit_num(r):
> s = "%x"%r
> return len(s) * 4 - OFFSET[int(s[0],16)]
>
> P.S. Back home, this sort of 'nitpicking' would be judged
> unconstructive. Worth pointing out, or not worth saying?
>
> P.S.S. 'Thighest' bit? I thought the spam filters would catch that.
>
That should be P.P.S.
PS: This is also unconstructive nitpicking.
Kind regards
Rich ;)
- --
Rich Healey - iTReign \ .''`. / heale...@gmail.com
Developer / Systems Admin \ : :' : / heale...@itreign.com
AIM: richohealey33 \ `. `' / ri...@psych0tik.net
MSN: bitcho...@hotmail.com \ `- / richo...@hellboundhackers.org
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (MingW32)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iEYEARECAAYFAkjpVZUACgkQLeTfO4yBSAcgeACgr45Hu4XKyMjCf0jwq1LR35tU
Lv8AnRn2RgHCxJ3QwYpNO8/DjLncKv2t
=/WZa
-----END PGP SIGNATURE-----
Aaron "Castironpi" Brady
wrote:
> Duncan Booth wrote:
> > mmgar...@gmx.de wrote:
>
> > OFFSET = dict(("%x"%i, int(c)) for i,c in enumerate("5433222211111111"))
> > def get_highest_bit_num(r):
> > s = "%x"%r
> > return len(s) * 4 - OFFSET[s[0]]
>
> def get_highest_bit_num(r):
> s = "%x"%r
> return len(s) * 4 - OFFSET[int(s[0],16)]
That's really counterintuitive. (That's the word, yes.) They're both
function calls and both global variables. Maybe you could use 'len(s)
* 4' to mask out the rest and lookup that index, rather than
converting -back- to integer. Or, better yet, take 'ord' of s[0].
(Ha ha, -you- time it.)
Aaron "Castironpi" Brady
> > P.S. Back home, this sort of 'nitpicking' would be judged
> > unconstructive. Worth pointing out, or not worth saying?
>
> > P.S.S. 'Thighest' bit? I thought the spam filters would catch that.
>
> That should be P.P.S.
>
> PS: This is also unconstructive nitpicking.
>
> Kind regards
>
> Rich ;)
Hey, whatever gets the bills paid, friend.
Duncan Booth
No, the difference between the two is still an extra call to a global
function.
'ord' may be slightly faster than calling 'int' (function calls with two
arguments are slower than similar functions with only one), but you have
still added one extra variable lookup and function call over the original.
--
Duncan Booth http://kupuguy.blogspot.com
Mark Dickinson
> Your point, that taking floor(log2(x)) is redundant, is a good catch.
> However, you should have added 'untested' ;-). When value has more
> significant bits than the fp mantissa can hold, this expression can be 1
> off (but no more, I assume). The following correction should be
> sufficient:
>
> res = math.frexp(value)[1] - EXP_OF_ONE
> test = 1<<res
> if test > r: res -= 1
> elif 2*test < r: res += 1
>
> For value = 2**n -1, n > 53, it is always 1 too high on my Intel
> machine, so the first correction is sometimes needed. I do not know if
> the second is or not.
See also http://bugs.python.org/issue3439
where there's a proposal to expose the _PyLong_NumBits method. This
would give an O(1) solution.
Mark
bearoph...@lycos.com
> See alsohttp://bugs.python.org/issue3439
> where there's a proposal to expose the _PyLong_NumBits method. This
> would give an O(1) solution.
Sounds useful, I've used the gmpy.numdigits(x [,base]) few times.
Bye,
bearophile
Holger
> See alsohttp://bugs.python.org/issue3439
> where there's a proposal to expose the _PyLong_NumBits method. This
> would give an O(1) solution.
Anyway, here's a pretty one (I think):
def highest_bit(n, maxbits = 256):
bit = 0
while maxbits > 1:
maxbits = maxbits >> 1
mask_b = ((1<<maxbits)-1)
mask_a = mask_b<<maxbits
a = n & mask_a
b = n & mask_b
if a:
bit = bit + maxbits
n = a >> maxbits
else:
n = b
return bit
I suspect you would call that a O(logn)) solution
Holger
Holger
bit = 0
while maxbits > 1:
a = n >> maxbits
if a:
bit += maxbits
n = a
return bit
is sligtly better
M.-A. Lemburg
In Python 2.6, you can use the bin() builtin:
>>> len(bin(1<<159)) - 3
159
--
Marc-Andre Lemburg
eGenix.com
Professional Python Services directly from the Source (#1, Oct 06 2008)
>>> Python/Zope Consulting and Support ... http://www.egenix.com/
>>> mxODBC.Zope.Database.Adapter ... http://zope.egenix.com/
>>> mxODBC, mxDateTime, mxTextTools ... http://python.egenix.com/
________________________________________________________________________
:::: Try mxODBC.Zope.DA for Windows,Linux,Solaris,MacOSX for free ! ::::
eGenix.com Software, Skills and Services GmbH Pastor-Loeh-Str.48
D-40764 Langenfeld, Germany. CEO Dipl.-Math. Marc-Andre Lemburg
Registered at Amtsgericht Duesseldorf: HRB 46611
Fredrik Johansson
> Hi,
>
> My question to the group: Does anyone know of a non-hackish way to
> determine the required bit position in python? I know that my two
> ideas
> can be combined to get something working. But is there a *better* way,
> that isn't that hackish?
No non-hackish way.
I've myself needed a version of this function for a speed-critical
application. For my purposes, it needs to be fast both for small and
extremely large numbers; the following is the fastest version I've
come up with. The idea to use bisect with a precomputed list when
possible, and math.log (with a correction) for larger numbers. There's
a tradeoff: a longer bisect table makes it fast for larger number, but
the bisection also becomes slower for small numbers. For my
application, 300 turned out to be a reasonable compromise.
from bisect import bisect
from math import log
powers = [1<<_ for _ in range(300)]
def bitcount(n):
bc = bisect(powers, n)
if bc != 300:
return bc
bc = int(log(n, 2)) - 4
return bc + bctable[n>>bc]
bctable = map(bitcount, range(1024))
Calling this function is still slow, so when possible, I track the
approximate number of bits in a number across operations, and do (bc
+bctable[n>>bc]) inline (where bc is a low estimate of the number of
bits) to obtain the exact bit count.
Fredrik
Aaron "Castironpi" Brady
> On Oct 5, 11:40 pm, Terry Reedy <tjre...@udel.edu> wrote:
>
> > Your point, that taking floor(log2(x)) is redundant, is a good catch.
> > However, you should have added 'untested' ;-). When value has more
> > significant bits than the fp mantissa can hold, this expression can be 1
> > off (but no more, I assume). The following correction should be
> > sufficient:
>
> > res = math.frexp(value)[1] - EXP_OF_ONE
> > test = 1<<res
> > if test > r: res -= 1
> > elif 2*test < r: res += 1
>
> > For value = 2**n -1, n > 53, it is always 1 too high on my Intel
> > machine, so the first correction is sometimes needed. I do not know if
> > the second is or not.
>
> where there's a proposal to expose the _PyLong_NumBits method. This
> would give an O(1) solution.
>
> Mark
That generates an odd error with ctypes.
>>> from ctypes import *
>>> _PyLong_NumBits= PYFUNCTYPE( c_int, py_object )( pythonapi._PyLong_NumBits )
>>> _PyLong_NumBits( 1<<50 )
Traceback (most recent call last):
File "_ctypes/callbacks.c", line 295, in 'calling callback function'
ctypes.ArgumentError: argument 1: <type 'exceptions.OverflowError'>:
long int to
o long to convert
2227205
>>>
Seems 'ctypes' tries to call PyLong_AsUnsignedLong for you. Anyone
know a way around it?
Thomas Heller
Here is ctypes code that works (tested with Python 2.5):
from ctypes import *
_PyLong_NumBits = pythonapi._PyLong_NumBits
_PyLong_NumBits.argtypes = py_object,
_PyLong_NumBits.restype = c_int
for i in range(64):
x = 1 << i
print i, _PyLong_NumBits(long(x))
Thomas
mmga...@gmx.de
> where there's a proposal to expose the _PyLong_NumBits method. This
> would give an O(1) solution.
> > In every case I can think of, I've wanted (0).numbits() to be 0.
Here is surely the wrong place to respond to
http://bugs.python.org/msg71384
but I want to make clear that I think that (0).numbits()==-1
is the natural solution. At least for all square-and-multiply-like
algorithms needed in cryptography (modular exponentiation, point
multiplication
on elliptic curves, generation of lucas numbers, etc) this property
of .numbits()
would be needed.
Mark Dickinson
> but I want to make clear that I think that (0).numbits()==-1
> is the natural solution. At least for all square-and-multiply-like
Can you clarify this? Why is -1 the natural solution? I
can see a case for 0, for -infinity (whatever that means),
or for raising an exception, but I can't see why -1 would
be at all useful or natural.
Here's a straightforward (mildly inefficient)
implementation of the left-to-right square-and-multiply algorithm
for powering. It works just fine with nbits(0) == 0.
def nbits(n):
return 0 if n == 0 else len(bin(abs(n)))-2
def LtoRpow(a, n):
acc = 1
for i in reversed(xrange(nbits(n))):
acc *= acc
if n & (1<<i):
acc *= a
return acc
MRAB
> On Oct 7, 5:19 pm, mmgar...@gmx.de wrote:
>
> > but I want to make clear that I think that (0).numbits()==-1
> > is the natural solution. At least for all square-and-multiply-like
> > algorithms needed in [...]
>
> Can you clarify this? Why is -1 the natural solution? I
> can see a case for 0, for -infinity (whatever that means),
> or for raising an exception, but I can't see why -1 would
> be at all useful or natural.
>
Compare it with, say, str.find, which returns the position if found
(>=0) or -1 if not found.
int.numbits should return the position of the highest set bit (>=0) or
-1 if none found.
On the other hand, if you compare it wirh str.index then int.numbits
should raise ValueError if none found.
Actually, the name "numbits" suggests that it returns the number of
bits, so (1).numbits() should return 1 and (0).numbits() should return
0. If it's called "highbit" then it suggests that it returns the
position of the highest (set) bit, so (1).highbit() should return 0
and (0).highbit() should return -1 (or raise an exception).
Terry Reedy
> On Oct 8, 9:56 am, Mark Dickinson <dicki...@gmail.com> wrote:
>> On Oct 7, 5:19 pm, mmgar...@gmx.de wrote:
>>
>>> but I want to make clear that I think that (0).numbits()==-1
>>> is the natural solution. At least for all square-and-multiply-like
>>> algorithms needed in [...]
>> Can you clarify this? Why is -1 the natural solution? I
>> can see a case for 0, for -infinity (whatever that means),
>> or for raising an exception, but I can't see why -1 would
>> be at all useful or natural.
>>
> [snip]
> Compare it with, say, str.find, which returns the position if found
> (>=0) or -1 if not found.
str.find is an historical anomaly that should not be copied. It
was(is?) a wrapper for C's string find function. C routinely uses -1 to
mean None for functions statically typed to return ints. The Python
version logically should return None and usually does for other functions.
greg
> str.find is an historical anomaly that should not be copied. It
> was(is?) a wrapper for C's string find function. C routinely uses -1 to
> mean None for functions statically typed to return ints. The Python
> version logically should return None and usually does for other functions.
Although Guido has defended it on the grounds that it can
be inconvenient having a function that returns different
types under different circumstances. Also it discourages
making the mistake of treating the return value as a
boolean.
--
Greg
Terry Reedy
> Terry Reedy wrote:
>
>> str.find is an historical anomaly that should not be copied. It
>> was(is?) a wrapper for C's string find function. C routinely uses -1
>> to mean None for functions statically typed to return ints. The
>> Python version logically should return None and usually does for other
>> functions.
I consider str.find to be an anomaly in two senses.
First, it is the only function/method I can think of that directly
duplicates another function/method by replace raising an exception with
returning an error indicator. Some developers wanted to drop it from
3.0, and I too wish it had been. We get along fine without list.find
and a whole slew of other such duplicates that one could think of.
Second, it is the only function/method I can think of that follows the
Unix/C convention of using '-1' as an error/exception/no-can-do
indicator. When it is so used, it is not really an int, but an error
indication represented as an int because there is no other choice. In
Python, there is another choice -- None -- which is used routinely,
including its use as the default return when there is nothing else to
return.
> Although Guido has defended it on the grounds that it can
> be inconvenient having a function that returns different
> types under different circumstances. Also it discourages
> making the mistake of treating the return value as a
> boolean.
I consider this backwards. Since -1 is a legal index in Python (unlike
some other languages) as well as a legal int, returning -1 allows if not
encourages the mistake of treating the fake return value as if it were a
real value. Returning None would completely prevent any use of the
error indicator other than to test it, which is the only thing one
should be able to do with it. It should not be usable as an index or
number in further calculations. I consider it a principle that error
indicators that are returned rather than raised should be an
illegal-to-use value if not a different type.
As for convenience, "if s.find(t) is None:" is as easily to write (and
clearer to read) as "if s.find(t) == -1:". As far as I can see,
different return types are only an issue, if at all, if values of both
types are to be used in further calculations.
Terry Jan Reedy
Aaron "Castironpi" Brady
> Terry Reedy wrote:
> > str.find is an historical anomaly that should not be copied. It
> > was(is?) a wrapper for C's string find function. C routinely uses -1 to
> > mean None for functions statically typed to return ints. The Python
> > version logically should return None and usually does for other functions.
>
> [I]t can
> be inconvenient having a function that returns different
> types under different circumstances.
No. It has precedent and there is no cost to convenience in pure
Python.
Perhaps you are passing the result straight to a C extension, and
parsing it straight to integer, but I can't attest to how common that
use case is.
mmga...@gmx.de
>> I think that (0).numbits()==-1 is the natural solution.
>
> can see a case for 0, for -infinity (whatever that means),
> or for raising an exception, but I can't see why -1 would
> be at all useful or natural.
You are right. I misunderstood the definition of nbits(). I initially
had asked for a function get_highest_bin_num(), which is always one
off
nbits() as it seems. I correct my sentence to
The choice get_highest_bin_num(0) == -1 is the natural one (in
concerns of cryptography). This property is needed for the
algorithms I listed above.
If get_highest_bit_num(n) == nbits(n) - 1 holds for all n >= 0 then
we
both agree.
I cite from MRAB's post:
> int.numbits should return the position of the highest set bit (>=0)
> or -1 if none found.
It seems that MRAB had the same misunderstanding.
Perhaps one should implement both: numbits() and get_highest_bit_num()
where
numbits(0) = 0 and get_highest_bit_num(0) raises an exception?
Nick Mellor
> mmgar...@gmx.de wrote:
> > Hi,
>
> > I'm using python to develop some proof-of-concept code for a
> > cryptographic application. My code makes extended use of python's
> > native bignum capabilities.
>
> > In many cryptographic applications there is the need for a function
> > 'get_highest_bit_num' that returns the position number of the highest
> > set bit of a given integer. For example:
>
> > get_highest_bit_num( (1 << 159)) == 159
> > get_highest_bit_num( (1 << 160) - 1) == 159
> > get_highest_bit_num( (1 << 160)) == 160
>
>
>
>
> >>> from bisect import bisect
> >>> BITS = [1<<n for n in range(1,1000)] # Use max number of bits here.
> >>> bisect(BITS, 1<<159)
> 159
> >>> bisect(BITS, 1<<160-1)
> 159
> >>> bisect(BITS, 1<<160)
> 160
>
> I have no clue if this is faster or not. The comparison function used
> in the search is (potentially) slow, but the search is O(log n) on the
> number of bits rather than O(n), so its worth a test.
>
> If you run timing test, let us know the results.
>
> Gary Herron
>
> > I implemented this the following way:
>
> > def get_highest_bit_num(r):
> > i = -1
> > while r > 0:
> > r >>= 1
> > i = i + 1
> > return i
>
> > This works, but it is a very unsatisfying solution, because it is so
> > slow.
>
> > My second try was using the math.log function:
>
> > import math
> > r = (1 << 160) - 1
> > print highest_bit_num(r) # prints out 159
> > print math.floor(math.log(r, 2)) # prints out 160.0
>
> > We see that math.log can only serve as a heuristic for the highest bit
> > position. For small r, for example r = (1 << 16) - 1, the result from
> > math.log(, 2) is correct, for big r it isn't any more.
>
> > determine the required bit position in python? I know that my two
> > ideas
> > can be combined to get something working. But is there a *better* way,
> > that isn't that hackish?
>
> > mmg
> > --
> >http://mail.python.org/mailman/listinfo/python-list
>
>
The following might be worth a try. It's faster the fewer set bits
there are in the original number, and lightning fast if there are only
one or two:
def get_highest_bit_num(i):
while i>0: highestbit, i = i, i & (i-1)
return highestbit
>>> highestbit(1<<31)
2147483648L
>>> highestbit(1<<4)
16
>>> highestbit(3<<4)
32
Note that it returns the value of the highest bit, not its position.
All it's doing is successively ANDing i with (i-1) until i is zero,
then returning the previous value of i.
It works because i & (i-1) has a useful property: it returns i less
its least significant set bit:
i=6 (binary 110) => i & (i-1)==4 (binary 100)
i=3328 => (binary 1101_0000_0000) then i & (i-1)==3072 (binary
1100_0000_0000)
(underscores for readability)
As far as I know there isn't another piece of logic that helps you
extract the most significant bit as simply :-)
Best wishes,
Nick
Mensanator
wrote:
import gmpy
print 'highest bit position: %d' % (len(gmpy.digits(3328,2))-1)
highest bit position: 11
or in 2.6
print 'highest bit position: %d' % (len(bin(3328)[2:])-1)
highest bit position: 11
>
> Best wishes,
>
> Nick
Mensanator
> On approximately 10/29/2008 11:51 AM, came the following characters from
> the keyboard of Mensanator:
>
> > or in 2.6
>
> > print 'highest bit position: %d' % (len(bin(3328)[2:])-1)
>
> > highest bit position: 11
>
Good question. Now that I think about it, I believe I learned of
it here, never saw it in the docs.
> Searching the Python 2.6 docs
> for bin found lots of things that start with bin, but none of them were
> bin. Searching the builtins page manual didn't find it. Is this a bug
> in the documentation?
Well ,it's mentioned in "What's new in Python 2.6":
<quote>
Python 3.0 adds several new built-in functions
and change the semantics of some existing built-ins.
Entirely new functions such as bin() have simply
been added to Python 2.6, but existing built-ins
haven’t been changed;
</quote>
You would think when you add a new function, you would
also add it's documentation, but maybe that was an
oversight. I don't have 3.0, but maybe it can be found
in that set of docs.
>
> --
> Glenn --http://nevcal.com/
> ===========================
> A protocol is complete when there is nothing left to remove.
> -- Stuart Cheshire, Apple Computer, regarding Zero Configuration Networking
Terry Reedy
> You would think when you add a new function, you would
> also add it's documentation, but maybe that was an
> oversight. I don't have 3.0, but maybe it can be found
> in that set of docs.
3.0c1
>>> help(bin)
Help on built-in function bin in module builtins:
bin(...)
bin(number) -> string
Return the binary representation of an integer or long integer.
Manual
bin(x)
Convert an integer number to a binary string. The result is a valid
Python expression. If x is not a Python int object, it has to define an
__index__() method that returns an integer.
You can file a doc bug for whatever is missing in 2.6. You might check
other 3.0 builtins that were backported.
tjr