Find First Set - Algorithms

Algorithms

Where find first set or a related function is not available in hardware, it must be implemented in software. The simplest implementation of ffs uses a loop:

function ffs (x) if x = 0 return 0 t ← 1 r ← 1 while (x & t) = 0 t ← t << 1 r ← r + 1 return r

where "<<" denotes left-shift. Similar loops can be used to implement all the related operations. On modern architectures this loop is inefficient due to a large number of conditional branches. A lookup table can eliminate most of these:

table = ffs(i) for i in 0..2n-1 function ffs_table (x) if x = 0 return 0 r ← 0 loop if (x & (2n-1)) ≠ 0 return r + table x ← x >> n r ← r + n

The parameter n is fixed (typically 8) and represents a time-space tradeoff. The loop may also be fully unrolled.

An algorithm for 32-bit ctz by Leiserson, Prokop, and Randall uses de Bruijn sequences to construct a minimal perfect hash function that eliminates all branches:

table initialized by: for i from 0 to 31: table ← i function ctz_debruijn (x) return table

The expression (x & (-x)) again isolates the least-significant 1 bit. There are then only 32 possible words, which the unsigned multiplication and shift hash to the correct position in the table. (Note: this algorithm does not handle the zero input.) A similar algorithm works for log base 2, but rather than isolate the most-significant bit, it rounds up to the nearest integer of the form 2n−1 using shifts and bitwise ORs:

table = {0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31} function lg_debruijn (x) for each y in {1, 2, 4, 8, 16}: x ← x | (x >> y) return table

Both the count leading zeros and count trailing zeros operations admit binary search implementations which take a logarithmic number of operations and branches, as in these 32-bit versions:

function clz (x) if x = 0 return 32 n ← 0 if (x & 0xFFFF0000) = 0: n ← n + 16, x ← x << 16 if (x & 0xFF000000) = 0: n ← n + 8, x ← x << 8 if (x & 0xF0000000) = 0: n ← n + 4, x ← x << 4 if (x & 0xC0000000) = 0: n ← n + 2, x ← x << 2 if (x & 0x80000000) = 0: n ← n + 1, x ← x << 1 return n function ctz (x) if x = 0 return 32 n ← 0 if (x & 0x0000FFFF) = 0: n ← n + 16, x ← x >> 16 if (x & 0x000000FF) = 0: n ← n + 8, x ← x >> 8 if (x & 0x0000000F) = 0: n ← n + 4, x ← x >> 4 if (x & 0x00000003) = 0: n ← n + 2, x ← x >> 2 if (x & 0x00000001) = 0: n ← n + 1, x ← x >> 1 return n

These can be assisted by a table as well, replacing the last four lines of each with a table lookup on the high/low byte.

Just as count leading zeros is useful for software floating point implementations, conversely, on platforms that provide hardware conversion of integers to floating point, the exponent field can be extracted and subtracted from a constant to compute the count of leading zeros. Corrections are needed to account for rounding errors.