Using de Bruijn Sequences to Index a 1 in a Computer Word
Using de Bruijn Sequences to Index a 1 in a Computer Word
复制标题
使用 de Bruijn 序列对计算机单词中的 1 进行索引
DOI：
--
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
K. H. Randall
中科院分区：
文献类型：
--
作者：
C. Leiserson;H. Prokop;K. H. Randall
有些计算机提供一条指令，在计算机字中查找1的索引，但许多计算机不这样做。本文提出了一种基于de Bruijn序列的快速算法来解决这个问题。该算法只涉及一个整数乘法和一个小表中的查找。我们比较我们的算法与其他流行的策略，使用表查找或浮点转换的性能。
Some computers provide an instruction to nd 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 a lookup in a small table. We compare the performance of our algorithm with other popular strategies that use table lookups or oating-point conversion.