Find First Set - Properties and Relations

Properties and Relations

The count trailing zeros and find first set operations are related by ctz(x) = ffs(x) - 1 (except for the zero input). Given w bits per word, the log base 2 is easily computed from the clz and vice versa by lg(x) = w - 1 - clz(x).

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 log base 2 operation such as M68000, ctz can be computed by:

ctz(x) = lg(x & (-x))

where "&" denotes bitwise AND and "-x" denotes the negative of x treating x as a signed integer in twos complement arithmetic. The expression x & (-x) clears all but the least-significant 1 bit, so that the most- and least-significant 1 bit are the same.

On platforms with an efficient count leading zeros operation such as ARM and PowerPC, ffs can be computed by:

ffs(x) = w - clz(x & (-x)).

Conversely, clz can be computed using ctz by first rounding up to the nearest power of two using shifts and bitwise ORs, as in this 32-bit example (note that this example depends on ctz returning 32 for the zero input):

function clz(x): for each y in {1, 2, 4, 8, 16}: x ← x | (x >> y) return 32 - ctz(x + 1)

On platforms with an efficient Hamming weight (population count) operation such as SPARC's POPC or Blackfin's ONES, ctz can be computed using the identity:

ctz(x) = pop((x & (-x)) - 1),

ffs can be computed using:

ffs(x) = pop(x ^ (~(-x)))

where "^" denotes bitwise xor, and clz can be computed by:

function clz(x): for each y in {1, 2, 4, 8, 16}: x ← x | (x >> y) return 32 - pop(x)

The inverse problem (given i, produce an x such that ctz(x)=i) can be computed with a left-shift (1 << i).

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 ffs/ctz/clz) or not all-one (for ffz/clo/cto) is encountered. A tree data structure that recursively uses bitmaps to track which words are nonzero can accelerate this.