\hypertarget{FFS_8ih}{
\section{FFS.ih File Reference}
\label{FFS_8ih}\index{FFS.ih@{FFS.ih}}
}
Find First (Last) Set Bit in a 32-bit word.  


{\tt \#include $<$PBI/FFS.ih$>$}\par


\subsection{Detailed Description}
Find First (Last) Set Bit in a 32-bit word. 

\begin{Desc}
\item[Author:]JJRussell - \href{mailto:russell@slac.stanford.edu}{\tt russell@slac.stanford.edu}\end{Desc}


\footnotesize\begin{verbatim}

    CVS $Id: FFS.ih,v 1.4 2011/03/24 23:05:41 apw Exp $
\end{verbatim}
\normalsize


{\bf SYNOPSIS} \par
 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.

\begin{itemize}
\item FFSL (w) - Find First Set Leading MSb = 0\item FFSl (w) - Find First Set leading LSb = 0\item FFST (w) - Find First Set Trailing MSb = 0\item FFSt (w) - Find First Set Trailing LSb = 0\item CNTLZ(w) - Count leading zeros, returns 32 if w = 0\item CNTTZ(w) - Count trailing zeros, returns 32 if w = 0\end{itemize}


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



\footnotesize\begin{verbatim}
                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
   \end{verbatim}
\normalsize


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

{\bf IMPLEMENTATION} {\bf NOTE} \par
 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).

{\bf Demonstration} {\bf of} {\bf the} {\bf methodk} \par
 Consider a 32-bit number with the following 8 bits pattern in its least significant bits



\footnotesize\begin{verbatim}
     x:      10110100
    ~x:      01001011
    -x:      01001100
    x & -x:  00000100  <- Only bit left standing was the lowest order
                          bit with a 1 in it
   \end{verbatim}
\normalsize