how to get the thighest bit position in big integers?

[Mensanator]

On Oct 29, 1:26 am, Nick Mellor <nick-gro... at back-pain-self-help.com>
wrote:
> 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 :-)

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