On 2008-10-05 17:26, [EMAIL PROTECTED] 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 > > 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?
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 -- http://mail.python.org/mailman/listinfo/python-list
