On Oct 6, 3:40 am, Gary Herron <[EMAIL PROTECTED]> wrote:
> [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
>
> 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
> > --
> >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
--
http://mail.python.org/mailman/listinfo/python-list
