E. El-Qawasmeh, M. Strauss, M. Mack, and S. Berkovich
Bit-counting, bit-parallelism, information retrieval, popcount
The operation of bit-counting, that is, determining the number of “1’s in a string of bits, is of significant importance for a number of computer applications such as coding theory, information retrieval, genetic algorithms, and file comparison. The growing importance of this operation has led to inclusion in recent computer systems of “popcount —dedicated hardware for bit population counting. In this paper, we introduce a new software scheme that enhances the most efficient algorithms for bit-counting. Using the suggested software technique, the speed of bit-counting approaches that of specialized hardware. Besides improving the performance of customary computer procedures, employing this software technique gives the designer an option of avoiding a dedicated popcount function unless otherwise clearly mandated for a particular application. Simplification of the processor construction would be more distinct as word size tends to increase beyond the 64-bit size. Hardware realization of bit-counting with larger words incurs a substantial extra complexity whereas for the suggested software technique this is not a problem.
Important Links:
Go Back
