Hi, I'm writing an app in python, and I'm storing some a lot of data in
bitmaps.
I need a way to find the first or latest set bit in a 64bit number, and
for that I've implemented a small routine.
Thing is that this routine is not as fast as I'd wish. I know most
processors implement BSF and BSR calls to do this efficiently.
Is there anyway to access those calls from python?
I'd still have my routine as a fallback on nonsupporting architectures.
Get a copy of the gmpy module.
Help on module gmpy:
NAME
gmpy
FILE
c:\program files\pygtk\python\lib\site-packages\gmpy.pyd
DESCRIPTION
gmpy 1.04 - General Multiprecision arithmetic for PYthon:
exposes functionality from the GMP 4 library to Python 2.{2,3,4}.
Allows creation of multiprecision integer (mpz), float (mpf),
and rational (mpq) numbers, conversion between them and to/from
Python numbers/strings, arithmetic, bitwise, and some other
higher-level mathematical operations; also, pretty good-quality
linear-congruential random number generation and shuffling.
mpz has comparable functionality to Python's builtin longs, but
can be faster for some operations (particularly multiplication
and raising-to-power) and has many further useful and speedy
functions (prime testing and generation, factorial, fibonacci,
binary-coefficients, gcd, lcm, square and other roots, ...).
mpf and mpq only offer basic arithmetic abilities, but they
do add the ability to have floating-point numbers ensuring at
least a predefined number of bits' worth of precision (and with
potentially-huge or extremely-tiny magnitudes), as well as
unlimited-precision rationals, with reasonably-fast operations,
which are not built-in features of Python.
FUNCTIONS (selected operations for binary use)
getbit(...)
getbit(x,n): returns 0 or 1, the bit-value of bit n of x;
n must be an ordinary Python int, >=0; x is an mpz, or else
gets coerced to one.
hamdist(...)
hamdist(x,y): returns the Hamming distance (number of bit-
positions
where the bits differ) between x and y. x and y must be mpz,
or else
get coerced to mpz.
lowbits(...)
lowbits(x,n): returns the n lowest bits of x; n must be an
ordinary Python int, >0; x must be an mpz, or else gets
coerced to one.
popcount(...)
popcount(x): returns the number of 1-bits set in x; note that
this is 'infinite' if x<0, and in that case, -1 is returned.
x must be an mpz, or else gets coerced to one.
scan0(...)
scan0(x, n=0): returns the bit-index of the first 0-bit of x
(that
is at least n); n must be an ordinary Python int, >=0. If no
more
0-bits are in x at or above bit-index n (which can only happen
for
x<0, notionally extended with infinite 1-bits), None is
returned.
x must be an mpz, or else gets coerced to one.
scan1(...)
scan1(x, n=0): returns the bit-index of the first 1-bit of x
(that
is at least n); n must be an ordinary Python int, >=0. If no
more
1-bits are in x at or above bit-index n (which can only happen
for
x>=0, notionally extended with infinite 0-bits), None is
returned.
x must be an mpz, or else gets coerced to one.
setbit(...)
setbit(x,n,v=1): returns a copy of the value of x, with bit n
set
to value v; n must be an ordinary Python int, >=0; v, 0 or !
=0;
x must be an mpz, or else gets coerced to one.
These work quite nicely. I use scan1() in the following idiom
which removes all factors of 2 in one fell swoop.
n = 3*n + 1 # always even, but how even?
f = gmpy.scan1(n) # bit position of LS 1-bit
n = n >> f # ...which is number of 0-bits
