Lowest/highest bit set in integer.

Updated Gribouillis 1 2K Views

These two functions compute the orders of the lowest bit and the highest bit set in the binary representation of an integer. I expect them to handle securely very large integer values.

#!/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)
Member Avatar for Gribouillis
Gribouillis 1,391 Programming Explorer

Hm my copy/paste operation missed a 'return k' in the dangling else at line 34. Sorry.

highbitorder.py_.zip (0.86 KB)
Edited by Gribouillis because: n/a
Member Avatar for Gribouillis
Gribouillis 1,391 Programming Explorer

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 by Gribouillis because: n/a
Member Avatar for Gribouillis
Gribouillis 1,391 Programming Explorer

Notice that in python 3, integers have a method bit_length() which computes the number of bits. The high_bit_order() could be obtained with

>>> n = 2368
>>> n.bit_length() - 1
11

See http://wiki.python.org/moin/BitManipulation for more info.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Edit Preview