In computer software and hardware, find first set (ffs) or find first one is a bit operation which returns the index or position of the least significant 'one' bit in its argument, counting from the least significant bit. A related operation is count trailing zeros (ctz) or number of trailing zeros (ntz), which counts the number of zero bits following the least significant one bit. There are two common variants of find first set, the POSIX definition which starts indexing of bits at 1, herein labelled ffs, and the variant which starts indexing of bits at zero, which is equivalent to ctz.
The operation which finds the index of the most significant set bit is log base 2, so called because it computes the binary logarithm . This is closely related to count leading zeros (clz) or number of leading zeros (nlz), which counts the number of zero bits preceding the most significant one bit.
Most modern CPU instruction set architectures provide one or more of these as hardware operators; software emulation is usually provided for the others, either as compiler intrinsics or in system libraries.
Examples Given the following 32-bit word:
The count trailing zeros operation would return 3, while the count leading zeros operation would return 16. The count leading zeros operation depends on the word size: if this 32-bit word were truncated to a 16-bit word, count leading zeros would return zero. The find first set operation would return 4, indicating the 4th position from the right. The logarithm of this number is log2 = , so the truncated base-2 logarithm is 15.
Similarly, given the bitwise negation of the above word:
The count trailing ones operation would return 3, the count leading ones operation would return 16, and the find first zero operation ffz would return 4.
If the word is zero (no bits set), count leading zeros and count trailing zeros both return the number of bits in the word, while ffs returns zero. Both log base 2 and zero-based implementations of find first set generally return an undefined result for the zero word.
Hardware support Many instruction set architectures include find first set or related operations. The most common operation is count leading zeros (clz); other operations can be implemented efficiently in terms of it (see Properties and relations).
Platform Mnemonic Name Operand widths Description On application to 0 ARM (ARMv5T architecture and later)except Cortex-M0/M0+/M1/M23 clz Count Leading Zeros 32 clz 32 ARM (ARMv8-A architecture) clz Count Leading Zeros 32, 64 clz Operand width AVR32 clz Count Leading Zeros 32 clz 32 DEC Alpha ctlz Count Leading Zeros 64 clz 64 cttz Count Trailing Zeros 64 ctz 64 Intel 80386 and later bsf Bit Scan Forward 16, 32, 64 ctz Undefined; sets zero flag bsr Bit Scan Reverse 16, 32, 64 Log base 2 Undefined; sets zero flag x86 supporting BMI1 or ABM lzcnt Count Leading Zeros 16, 32, 64 clz Operand width; sets carry flag x86 supporting BMI1 tzcnt Count Trailing Zeros 16, 32, 64 ctz Operand width; sets carry flag Itanium clz Count Leading Zeros 64 clz 64 MIPS32/MIPS64 clz Count Leading Zeros in Word 32, 64 clz Operand width clo Count Leading Ones in Word 32, 64 clo Operand width Motorola 68020 and later bfffo Find First One in Bit Field Arbitrary Log base 2 Field offset + field width PDP-10 jffo Jump if Find First One 36 clz 0; no operation (i.e., jumps on nonzero) POWER/PowerPC/Power ISA cntlz/cntlzw/cntlzd Count Leading Zeros 32, 64 clz Operand width Power ISA 3.0 and later cnttzw/cnttzd Count Trailing Zeros 32, 64 ctz Operand width RISC-V ("B" Extension) clz Count Leading Zeros 32, 64 clz Operand width ctz Count Trailing Zeros 32, 64 ctz Operand width SPARC Oracle Architecture 2011 and later lzcnt (synonym: lzd) Leading Zero Count 64 clz 64 VAX ffs Find First Set 0–32 ctz Operand width; sets zero flag IBM z/Architecture flogr Find Leftmost One 64 clz 64 vclz Vector Count Leading Zeroes 8, 16, 32, 64 clz Operand width vctz Vector Count Trailing Zeroes 8, 16, 32, 64 ctz Operand width
On some Alpha platforms CTLZ and CTTZ are emulated in software.
Tool and library support A number of compiler and library vendors supply compiler intrinsics or library functions to perform find first set and/or related operations, which are frequently implemented in terms of the hardware instructions above:
Tool/libraryNameTypeInput type(s)NotesOn application to 0C23 standard librarystdc_first_trailing_one[_uc,_us,_ui,_ul,_ull]stdc_trailing_zeros[_uc,_us,_ui,_ul,_ull]stdc_first_leading_one[_uc,_us,_ui,_ul,_ull]stdc_leading_zeros[_uc,_us,_ui,_ul,_ull]Library functionunsigned char,unsigned short,unsigned int,unsigned long,unsigned long longFunctions for zero and ones are also provided.0 (bit index)Operand width (count)C++20 standard librarybit_ceil bit_floorbit_widthcountl_zero countl_onecountr_zero countr_oneLibrary functionunsigned char,unsigned short,unsigned int,unsigned long,unsigned long long POSIX.1 compliant libc4.3BSD libcOS X 10.3 libcffsLibrary functionintIncludes glibc. POSIX does not supply the complementary log base 2 / clz.0FreeBSD 5.3 libcOS X 10.4 libcffslflsflslLibrary functionint,longfls("find last set") computes (log base 2) + 1.0FreeBSD 7.1 libcffsllflsllLibrary functionlong long 0GCC 3.4.0Clang 5.x__builtin_ffs[l,ll,imax]__builtin_clz[l,ll,imax]__builtin_ctz[l,ll,imax]Built-in functionsunsigned int,unsigned long,unsigned long long,uintmax_tGCC documentation considers result undefined clz and ctz on 0.0 (ffs)Visual Studio 2005_BitScanForward_BitScanReverseCompiler intrinsicsunsigned long,unsigned __int64Separate return value to indicate zero inputUndefinedVisual Studio 2008__lzcntCompiler intrinsicunsigned short,unsigned int,unsigned __int64Relies on hardware support for the lzcnt instruction introduced in BMI1 or ABM.Operand widthVisual Studio 2012_arm_clzCompiler intrinsicunsigned intRelies on hardware support for the clz instruction introduced in the ARMv5T architecture and later.?Intel C++ Compiler_bit_scan_forward_bit_scan_reverseCompiler intrinsicsint UndefinedNvidia CUDA__clzFunctions32-bit, 64-bitCompiles to fewer instructions on the GeForce 400 series32__ffs0LLVMllvm.ctlz.*llvm.cttz.*Intrinsic8, 16, 32, 64, 256LLVM assembly languageOperand width, if 2nd argument is 0; undefined otherwiseGHC 7.10 (base 4.8), in Data.BitscountLeadingZeroscountTrailingZerosLibrary functionFiniteBits b => bHaskell programming languageOperand widthRust standard libraryhighest_oneleading_zeroslowest_onetrailing_zerosLibrary methodAll primitive integer types and other integer types such as NonZero<T>highest_one and lowest_one are not yet stable.Zig@clz@ctzbuiltin functioninteger or vector
Properties and relations If bits are labeled starting at 1 (which is the convention used in this article), then count trailing zeros and find first set operations are related by (except when the input is zero). If bits are labeled starting at , then count trailing zeros and find first set are exactly equivalent operations. Given bits per word, the is easily computed from the and vice versa by .
As demonstrated in the example above, the find first zero, count leading ones, and count trailing ones operations can be implemented by negating the input and using find first set, count leading zeros, and count trailing zeros. The reverse is also true.
On platforms with an efficient log2 operation such as M68000, can be computed by:
where denotes bitwise AND and denotes the two's complement of . The expression clears all but the least-significant bit, so that the most- and least-significant bit are the same.
On platforms with an efficient count leading zeros operation such as ARM and PowerPC, can be computed by:
.
Conversely, on machines without or operators, can be computed using , albeit inefficiently:
(which depends on returning for the zero input)
On platforms with an efficient Hamming weight (population count) operation such as SPARC's POPC or Blackfin's ONES, there is:
, or ,
where denotes bitwise exclusive-OR, denotes bitwise OR and denotes bitwise negation.
The inverse problem (given , produce an such that ) can be computed with a left-shift ().
Find first set and related operations can be extended to arbitrarily large bit arrays in a straightforward manner by starting at one end and proceeding until a word that is not all-zero (for , , ) or not all-one (for , , ) is encountered. A tree data structure that recursively uses bitmaps to track which words are nonzero can accelerate this.
Software emulation Most CPUs dating from the late 1980s onward have bit operators for ffs or equivalent, but a few modern ones like some of the ARM Cortex-M processors do not. In lieu of hardware operators for ffs, clz and ctz, software can emulate them with shifts, integer arithmetic and bitwise operators. There are several approaches depending on architecture of the CPU and to a lesser extent, the programming language semantics and compiler code generation quality. The approaches may be loosely described as linear search, binary search, search+table lookup, de Bruijn multiplication, floating point conversion/exponent extract, and bit operator (branchless) methods. There are tradeoffs between execution time and storage space as well as portability and efficiency.
Software emulations are usually deterministic. They return a defined result for all input values; in particular, the result for an input of all zero bits is usually 0 for ffs, and the bit length of the operand for the other operations.
If one has a hardware clz or equivalent, ctz can be efficiently computed with bit operations, but the converse is not true: clz is not efficient to compute in the absence of a hardware operator.
2n The function (round up to the nearest power of two) using shifts and bitwise ORs is not efficient to compute as in this 32-bit example and even more inefficient if we have a 64-bit or 128-bit operand:
function pow2(x): if x = 0 return invalid // invalid is implementation defined (not in [0,63]) x ← x - 1 for each y in {1, 2, 4, 8, 16}: x ← x | (x >> y) return x + 1
FFS Since ffs = ctz + 1 (POSIX) or ffs = ctz (other implementations), the applicable algorithms for ctz may be used, with a possible final step of adding 1 to the result, and returning 0 instead of the operand length for input of all zero bits.
CTZ The canonical algorithm is a loop counting zeros starting at the LSB until a 1-bit is encountered:
function ctz1 (x) if x = 0 return w t ← 1 r ← 0 while (x & t) = 0 t ← t << 1 r ← r + 1 return r
This algorithm executes O(w) time and operations, and is impractical in practice due to a large number of conditional branches.
An exception is if the inputs are uniformly distributed. In that case, we can rely on the fact that half the return values will be 0, one quarter will be 1, and so on. The average number of loop iterations per function call is 1, and the algorithm executes in O(1) average-case time.
A lookup table can eliminate most branches:
table[1..2n-1] = ctz(i) for i in 1..2n-1 function ctz2 (x) if x = 0 return w r ← 0 while (x & (2n−1)) ≠ 0 x ← x >> n r ← r + n return r + table[x & (2n−1)]
The parameter n is fixed (typically 8) and represents a time–space tradeoff. The loop may also be fully unrolled. But as a linear lookup, this approach is still O(n) in the number of bits in the operand.
If n = 4 is chosen, the table of 16 2-bit entries can be encoded in a single 32-bit constant using SIMD within a register techniques:
// binary table ← 0x12131210 function ctz2a (x) if x = 0 return w r ← 0 while (x & 15) = 0 x ← x >> 4 r ← r + 4 return r + ((table >> 2*(x & 15)) & 3);
This technique is quite practical in applications such as the binary GCD algorithm, where the x values are uniformly distributed, so the iterative loop is not needed of the time, and suffers minimal branch misprediction penalty.