On Oct 29, 1:26 am, Nick Mellor <[EMAIL PROTECTED]> wrote: > 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 :-)
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 -- http://mail.python.org/mailman/listinfo/python-list