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)
About the Author