“Largest power of two less than N” in Python

Question

def floor_log(num, base):
    if num < 0:
       raise ValueError("Non-negative number only.")
    exponent = 0
    while num > 1:
        num >>= 1
        exponent += 1
    return base << (exponent - 1)

print floor_log(3, 2) #2 
print floor_log(4, 2) #4
print floor_log(5, 2) #4
print floor_log(6, 2) #4

I frequently miss the edge cases like while num or while num > 1. What is good strategy to avoiding these mistakes? apart from this the function seems fine to me. Comments are most welcome.

Answer 1

I am surprised you don't just use the math functions you have included in your function name... but, then I see that you have a real bug in your code too.

You declare a base parameter, but it only works if the base is the value 2. Bit Shifting is always a base-2 operation.

If you really want to find the largest base exponent less than num, then you should use the math library:

import math

def floor_log(num, base):
    if num < 0:
       raise ValueError("Non-negative number only.")

    if num == 0:
       return 0

    return base ** int(math.log(num, base))

Essentially, your code only works for base 2.

If you want to do a looping solution similar to your bitshifting, then try:

def floor_log(num, base):
    if num < 0:
       raise ValueError("Non-negative number only.")
    if num == 0:
       return 0

    exponent = 0
    while num >= base:
        num /= base
        exponent += 1
    return base ** exponent

You should probably add tests in there for special cases, like the input equals to base, or 1, or 0.

See the code running here in ideone

Answer 2

If what you really want is the "largest power of 2", you should make that more explicit:

def largest_power_of_two(n):

And does the largest power of two less than n mean in terms of bits? It's just dropping all of the bits except for the left-most one. Since we can get the bit length of a number directly, we can just do that:

def largest_power_of_two(n):
    return 1 << (n.bit_length() - 1)

If you want error check, you can add the value error if you want (note only positive ns are valid, you initially allowed for 0... but what is the largest power of 2 less than or equal to 0?):

def largest_power_of_two(n):
    if n > 0:
        return 1 << (n.bit_length() - 1)
    else:
        raise ValueError("only meaningful for positive values")

Don't write loops when you don't need to.

Answer 3

You can use Kernighan's set bit counting method to your advantage here:

def floor_log2(n):
    assert n > 0
    last = n
    n &= n - 1
    while n:
        last = n
        n &= n - 1
    return last

The key insight is that x & (x - 1) removes the least significant set bit from x, so you want to return the value prior to the iteration that removes the last set bit and hence makes x zero.

There's not really much of a point in this type of bit twiddling in Python code, but if you ever have to rewrite this for a lower level language. e.g. C, then writing the whole algorithm in terms of such simple elementary expressions typically has a big impact on performance.

Answer 4

I frequently miss the edge cases like while num or while num > 1.

You did that here. What if num is 0 or 1.75? You'll get a TypeError when your function performs num >>= 1 in the case num is 1.75, and maybe that's what you want. The function will return 0 in the case num is zero.

As others have noted, your function only works for base==2. If you truly meant a base 2 function only, then you shouldn't promise that you can handle any base. An alternative to using log for this base 2 logarithm is to use the fact that python provides a function available on all platforms (even those that don't use IEEE floating point) that does exactly what you want:

import math
def floor_log2 (num) :
    if (num <= 0) :
        raise ValueError("Positive number only.")
    mantissa, res = math.frexp(num)
    if (mantissa == 0.5) :
        res -= 1
    return res-1

This works because the job of math.frexp(x) is to

return the mantissa and exponent of x as the pair (m, e). m is a float and e is an integer such that x == m * 2**e exactly. If x is zero, returns (0.0, 0), otherwise 0.5 <= abs(m) < 1. This is used to “pick apart” the internal representation of a float in a portable way.

Your function and mine have a similar edge case behavior: The name does not quite agree with the return value in the case the input is an integer power of two (or integer power of the base in your case). The docstring should clear document the nature of the return value in these edge cases.

Finally, your function does not return the floor of the log base 2. It returns 2^{floor_log2(n)}. Renaming it largest_power_of_two,

import math
def largest_power_of_two (num) :
    """"Returns the integral power of two that is strictly less than num"""

    if (num <= 0) :
        raise ValueError("Positive number only.")
    mantissa, res = math.frexp(num)
    if (mantissa == 0.5) :
        res -= 1
    if res > 0 :
        return 1 << (res-1)
    else :
        return 1.0 / (1 << (1-res))