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.