## Using de Bruijn Sequences to Index a 1 in a Computer Word

Charles E. Leiserson

Harald Prokop

Keith H. Randall

[Full text in PDF, 200KB]

### Abstract

Some computers provide an instruction to find the index of a 1 in a
computer word, but many do not. This paper provides a fast and novel
algorithm based on de Bruijn sequences to solve this problem. The
algorithm involves little more than an integer multiply and lookup in
a small table. We compare the performance of our algorithm with other
popular strategies that use table lookups or floating-point
conversion.