Bit Scan Forward and Reverse

Discussion in 'Python' started by Thomas Dybdahl Ahle, Jan 18, 2008.

  1. 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.

    --
    Med venlig hilsen,
    Best regards,
    Thomas
     
    Thomas Dybdahl Ahle, Jan 18, 2008
    #1
    1. Advertising

  2. Thomas Dybdahl Ahle

    Matimus Guest

    On Jan 18, 12:01 pm, Thomas Dybdahl Ahle <> 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.
    >
    > --
    > Med venlig hilsen,
    > Best regards,
    > Thomas


    There isn't a simple way, but you have a couple of options:

    1. put the code in a dll and call it from ctypes.
    2. see extending and embedding in the documentation.

    Matt
     
    Matimus, Jan 18, 2008
    #2
    1. Advertising

  3. Thomas Dybdahl Ahle

    Guest

    On Jan 18, 2:01 pm, Thomas Dybdahl Ahle <> 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
     
    , Jan 18, 2008
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. dogbite
    Replies:
    4
    Views:
    702
    osmium
    Oct 10, 2003
  2. Replies:
    3
    Views:
    1,802
    Timothy Bendfelt
    Jan 19, 2007
  3. Jim Langston

    iterate forward OR reverse

    Jim Langston, Jul 2, 2005, in forum: C++
    Replies:
    8
    Views:
    439
    msalters
    Jul 4, 2005
  4. Replies:
    9
    Views:
    1,011
    Juha Nieminen
    Aug 22, 2007
  5. Robert Dodier

    Scan forward n lines from specified file offset

    Robert Dodier, Nov 5, 2006, in forum: Perl Misc
    Replies:
    3
    Views:
    85
    DJ Stunks
    Nov 6, 2006
Loading...

Share This Page