FFS.ih File Reference

Find First (Last) Set Bit in a 32-bit word. More...

#include <PBI/FFS.ih>

---

Detailed Description

Find First (Last) Set Bit in a 32-bit word.

Author:

JJRussell - russell@slac.stanford.edu

    CVS $Id: FFS.ih,v 1.4 2011/03/24 23:05:41 apw Exp $

SYNOPSIS
This routine provides an efficient implementation to find the first leading or trailing bit set in a 32-bit word. There are six routines defined.

• FFSL (w) - Find First Set Leading MSb = 0
• FFSl (w) - Find First Set leading LSb = 0
• FFST (w) - Find First Set Trailing MSb = 0
• FFSt (w) - Find First Set Trailing LSb = 0
• CNTLZ(w) - Count leading zeros, returns 32 if w = 0
• CNTTZ(w) - Count trailing zeros, returns 32 if w = 0

The convention is that the final letter designates whether the notional scan is a leading or trailing scan and whether the MSb or the LSb is designated as 0.

The interface is generic, but the implementation is machine and compiler dependent. The following table indicates on which platforms the routine maps into a single machine instruction

                PowerPC          Intel     All Others
       FFSL     cntlz         bsr ^ 31     C scan routine
       FFSl     FFSL ^ 31          bsr     C scan routine
       FFST     FFSL(x & -x)  bsf ^ 31     C scan routine
       FFSt     FFST ^ 31          bsf     C scan routine
   

The FFSL routine effectively counts the leading zeros, while the FFSt routine effectively counts the trailing zeros.

IMPLEMENTATION NOTE
Some implementation use the trick of preconditioning the input value (x => x & -x) to implement the trailing scan. This trick is courtesy of the fine 'gcc' folks. It takes a minute to understand how this works.

Consider an arbitrary word and first focus on the trailing bits. One a twos-complement machine, negation consists of first complementing the bits, then adding one. So, again thinking of the low order bits, the complement turns all the 0's to 1's and all the 1's to 0's. Imagine a string of 0's in the low order bits. These bits all turn to 1's under the complement. Adding 1's generates a 0 and a carry into the next bit until a 0 (which in the original un-complemented word was the first 1) is encountered. The bits above the first 1 are now the complement of the original pattern, so the 'and' operation eliminates these, leaving only one bit standing, the bit with the first one. One now just uses the FFSL to find this bit. It is a trivial manner to turn the result of FFSL to the correct result of FFSt (it is already the right answer for FFST).

Demonstration of the methodk
Consider a 32-bit number with the following 8 bits pattern in its least significant bits

     x:      10110100
    ~x:      01001011
    -x:      01001100
    x & -x:  00000100  <- Only bit left standing was the lowest order
                          bit with a 1 in it