how to get the thighest bit position in big integers?

[greg]

str.find is an historical anomaly that should not be copied. It
was(is?) a wrapper for C's string find function. C routinely uses -1 to
mean None for functions statically typed to return ints. The Python
version logically should return None and usually does for other functions.

Although Guido has defended it on the grounds that it can
be inconvenient having a function that returns different
types under different circumstances. Also it discourages
making the mistake of treating the return value as a
boolean.

 

[Terry Reedy]

I consider str.find to be an anomaly in two senses.

First, it is the only function/method I can think of that directly
duplicates another function/method by replace raising an exception with
returning an error indicator. Some developers wanted to drop it from
3.0, and I too wish it had been. We get along fine without list.find
and a whole slew of other such duplicates that one could think of.

Second, it is the only function/method I can think of that follows the
Unix/C convention of using '-1' as an error/exception/no-can-do
indicator. When it is so used, it is not really an int, but an error
indication represented as an int because there is no other choice. In
Python, there is another choice -- None -- which is used routinely,
including its use as the default return when there is nothing else to
return.

Although Guido has defended it on the grounds that it can
be inconvenient having a function that returns different
types under different circumstances. Also it discourages
making the mistake of treating the return value as a
boolean.

I consider this backwards. Since -1 is a legal index in Python (unlike
some other languages) as well as a legal int, returning -1 allows if not
encourages the mistake of treating the fake return value as if it were a
real value. Returning None would completely prevent any use of the
error indicator other than to test it, which is the only thing one
should be able to do with it. It should not be usable as an index or
number in further calculations. I consider it a principle that error
indicators that are returned rather than raised should be an
illegal-to-use value if not a different type.

As for convenience, "if s.find(t) is None:" is as easily to write (and
clearer to read) as "if s.find(t) == -1:". As far as I can see,
different return types are only an issue, if at all, if values of both
types are to be used in further calculations.

Terry Jan Reedy

 

[Aaron \Castironpi\ Brady]

str.find is an historical anomaly that should not be copied.  It
was(is?) a wrapper for C's string find function.  C routinely uses -1 to
mean None for functions statically typed to return ints.  The Python
version logically should return None and usually does for other functions.

....
t can
be inconvenient having a function that returns different
types under different circumstances.

....

No. It has precedent and there is no cost to convenience in pure
Python.

Perhaps you are passing the result straight to a C extension, and
parsing it straight to integer, but I can't attest to how common that
use case is.

 

[mmgarvey]

Can you clarify this?  Why is -1 the natural solution? I
can see a case for 0, for -infinity (whatever that means),
or for raising an exception, but I can't see why -1 would
be at all useful or natural.

You are right. I misunderstood the definition of nbits(). I initially
had asked for a function get_highest_bin_num(), which is always one
off
nbits() as it seems. I correct my sentence to

The choice get_highest_bin_num(0) == -1 is the natural one (in
concerns of cryptography). This property is needed for the
algorithms I listed above.

If get_highest_bit_num(n) == nbits(n) - 1 holds for all n >= 0 then
we
both agree.

I cite from MRAB's post:

int.numbits should return the position of the highest set bit (>=0)
or -1 if none found.

It seems that MRAB had the same misunderstanding.

Perhaps one should implement both: numbits() and get_highest_bit_num()
where
numbits(0) = 0 and get_highest_bit_num(0) raises an exception?

 

[Nick Mellor]

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

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
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

 

[Mensanator]

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

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

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

 

[Glenn Linderman]

or in 2.6

print 'highest bit position: %d' % (len(bin(3328)[2:])-1)

highest bit position: 11

This works, but where is it documented? Searching the Python 2.6 docs
for bin found lots of things that start with bin, but none of them were
bin. Searching the builtins page manual didn't find it. Is this a bug
in the documentation?

 

[Mensanator]

or in 2.6

print 'highest bit position: %d' % (len(bin(3328)[2:])-1)

highest bit position: 11

This works, but where is it documented?  

Good question. Now that I think about it, I believe I learned of
it here, never saw it in the docs.

Searching the Python 2.6 docs
for bin found lots of things that start with bin, but none of them were
bin.  Searching the builtins page manual didn't find it.  Is this a bug
in the documentation?

Well ,it's mentioned in "What's new in Python 2.6":
<quote>
Python 3.0 adds several new built-in functions
and change the semantics of some existing built-ins.
Entirely new functions such as bin() have simply
been added to Python 2.6, but existing built-ins
haven’t been changed;
</quote>

You would think when you add a new function, you would
also add it's documentation, but maybe that was an
oversight. I don't have 3.0, but maybe it can be found
in that set of docs.

 

[Terry Reedy]

You would think when you add a new function, you would
also add it's documentation, but maybe that was an
oversight. I don't have 3.0, but maybe it can be found
in that set of docs. 3.0c1

Help on built-in function bin in module builtins:

bin(...)
bin(number) -> string

Return the binary representation of an integer or long integer.

Manual
bin(x)
Convert an integer number to a binary string. The result is a valid
Python expression. If x is not a Python int object, it has to define an
__index__() method that returns an integer.

You can file a doc bug for whatever is missing in 2.6. You might check
other 3.0 builtins that were backported.

tjr

 

[Glenn Linderman]

Help on built-in function bin in module builtins:

bin(...)
bin(number) -> string

Return the binary representation of an integer or long integer.

2.6 does this too