ffs algorithm

This is a discussion on ffs algorithm within the C Programming forums, part of the General Programming Boards category; I have code, which works, to find the most significant bit set in an unsigned int. It's an ffs clone ...

  1. #1
    .
    Join Date
    Nov 2003
    Posts
    307

    ffs algorithm

    I have code, which works, to find the most significant bit set in an unsigned
    int. It's an ffs clone for systems without the non-standard libc ffs().
    Our other "bit" code uses bit twiddling and is fast. This one algorithm is
    about 300% slower. It's also slow on the boxes that do have it as part the math library
    version from libc.

    Since ffs is part of libc on only some of our boxes, and we need it everywhere, I
    reverse engineered it and got:

    Code:
        int
    ffs(unsigned int value)
        int exponent=floor(log2((double) value));
        return  exponent+1;
    }

    After googling I got, among other things (from D Neto) some
    promising code, or so it seemed.

    Code:
    ffs1(register unsigned int value)
    {
    	  int i=0;
        value |= value>>1;
        value |= value>>2;
        value |= value>>4;
        value |= value>>8;
        value |= value>>16;
      	value ^= (value>>1);
      	while(value)
      	{
      	    value=value>>1;
      	    i++;
      	}
      	return i;
    }
    Another try by me:
    Code:
    int ffs2(register unsigned int value){        
            register int i=0;
            if(value)                       
                for(i=1;~value&1;value=value>>1,++i);
            return i;
    }
    Profile says for 104,000,000 iterations ffs1() was 35% slower the ffs with math.
    ffs2() is about 5% faster than ffs() for the same test. -- not really significant.

    What am I missing?

    ffs() is part of the critical path in new code and needs improvement. Suggestions,
    changes, other algorithms?

    Thanks.

  2. #2
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    I'm not familiar with ffs, so I don't know how that might compare to some of the things here. One thing I do notice is that I don't get the same result with ffs1 as I do with ffs2. [EDIT]Well I guess they do if only one bit is set in the value.
    Last edited by Dave_Sinkula; 10-01-2004 at 01:59 PM.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  3. #3
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,499
    number of digits in number?
    Look at my first reply, and use the same technique to compare against powers of two to home in on the highest set bit.
    Should only take 5 comparisons for any 32 bit number.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  4. #4
    Registered User
    Join Date
    Aug 2003
    Posts
    470
    Intel has assembly instructions bsr and bsf.

  5. #5
    .
    Join Date
    Nov 2003
    Posts
    307
    Thanks guys.

    Bithack page I remember from years ago - good link.

    asm won't work -- too many platforms

    Salem's approach worked the most efficiently.

    Thanks. We have an old app that creates bit-encoded data and we have to ffs on 32 bit longs... way too many times. Otherwise it would not be an issue, and I'd let the compiler work it out. Run-time is now way less than 24 hours for a daily job, kind of an elementary requirement.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 01:30 AM
  2. Replies: 4
    Last Post: 12-10-2006, 06:08 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21