#!/usr/bin/env python
# -*-coding: utf8-*-
# Author: Gribouillis for the python forum at www.daniweb.com
# Created: 2012-01-14 11:44:25.230176 (isoformat date)
# License: Public Domain
# Use this code freely.

from math import log

def high_bit_order(n):
    """Return the integer k >= 0 such that 2**k <= n < 2**(k+1).

    This is also the order of the last bit set in the bitwise representation of n.
    Raise value error if n <= 0
        * for n == 0, no bit is set.
        * for n < 0, an infinite number of bits are set.
    For example
        high_bit_order(2368) --> 11
        n = 2368  bits: 000000101001000000000000000...
        n = -2368 bits: 000000110110111111111111111...
        n = 2**11 bits: 000000000001000000000000000...
    This function checks its return value and raise ValueError if an error
    is detected.
    """
    k = int(log(n, 2))
    if k:
        x = n >> (k-1)
        if x == 1: # correct log() imprecision for very large integers
            return k - 1
        elif 2 <= x < 4:
            return k
        else: # very unlikely, but handled
            raise ValueError("high_bit_order() failed on unusual value.")
    else:
        return k

def low_bit_order(n):
    """Return the largest integer k >= 0 such that 2**k divides n.
    
    This is also the order of the first bit set in the bitwise representation of n.
    Raise ValueError if n == 0. For negative n, the low_bit_order is the same for n and -n.
    For example:
        low_bit_order(2368) --> 6
        n = 2368  bits: 000000101001000000000000000...
        n = 2**6  bits: 000000100000000000000000000...
"""
    return high_bit_order(n & -n)

I discovered that math.log() returns different values for integers and long integers in python 2.7, for example

>>> repr(log(4L, 2))
'1.9999999999999998'
>>> repr(log(4, 2))
'2.0'

This caused a bug in high_bit_order() above. Here is a bugfix release which handles this case

from math import log
_hb_help_dict = dict(((1,-1), (2, 0), (3, 0), (4, 1)))

def high_bit_order(n):
    """Return the integer k >= 0 such that 2**k <= n < 2**(k+1).

    This is also the order of the last bit set in the bitwise representation of n.
    Raise value error if n <= 0
        * for n == 0, no bit is set.
        * for n < 0, an infinite number of bits are set.
    For example
        high_bit_order(2368) --> 11
        n = 2368  bits: 000000101001000000000000000...
        n = -2368 bits: 000000110110111111111111111...
        n = 2**11 bits: 000000000001000000000000000...
    """
    k = int(log(n, 2))
    try:
        return (k + _hb_help_dict[n >> (k-1)]) if k else k
    except KeyError: # very unlikely, but handled
        raise ValueError(("high_bit_order() failed on unusual value.", n))

Edited 4 Years Ago by Gribouillis: n/a

The article starter has earned a lot of community kudos, and such articles offer a bounty for quality replies.