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.
Lowest/highest bit set in integer.
#!/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)
Gribouillis 1,391 Programming Explorer Team Colleague
Hm my copy/paste operation missed a 'return k' in the dangling else at line 34. Sorry.
Gribouillis 1,391 Programming Explorer Team Colleague
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)) Gribouillis 1,391 Programming Explorer Team Colleague
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
11See 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.