how to get the thighest bit position in big integers?

[Nick Mellor]

On Oct 6, 3:40 am, Gary Herron <gher... at islandtraining.com> wrote:
> mmgar... at 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
>
> 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