Bit Scan Forward and Reverse

[mensanator at aol.com]

On Jan 18, 2:01 pm, Thomas Dybdahl Ahle <lob... at gmail.com> wrote:
> 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



>
> --
> Med venlig hilsen,
> Best regards,
> Thomas