A bit-counting algorithm using the frequency division principle

• Published in: Software, practice & experience practice & experience, 2000-11, Vol.30 (14), p.1531-1540
• Main Authors: Berkovich, Simon, Lapir, Gennadi M., Mack, Marilyn
• Format: Article
• Language: English
• Subjects: bit counting; bit-parallelism; document retrieval
• ISSN: 0038-0644; 1097-024X
• DOI: 10.1002/1097-024X(20001125)30:14<1531::AID-SPE347>3.0.CO;2-A

The paper addresses the omnipresent problem of bit counting. This problem is of particular importance for information systems where the choice of a rational access strategy may require repeated evaluation of the cardinalities of retrieved sets of data items. There are several different methods available to implement this procedure, which involve shifting, table look‐up, exploiting the properties of fixed point arithmetic, and manipulations with bitwise logical operations. This paper presents a novel approach to the organization of bit counting based on the principle of frequency division (FD). The developed algorithm emulates a set of 32 binary counters using the bit‐parallelism of computer word operations. The overflowing bits generated by these counters at a lower frequency are processed with the arithmetic‐logic method, which is most efficient for sparse binary vectors. The suggested FD procedure is one of the fastest among the known, widely available procedures for bit counting. In future computers, with 64‐bit words and larger, the gain in speed due to the FD technique will be higher, and the performance of this software could be comparable to that of specialized hardware. Copyright © 2000 John Wiley & Sons, Ltd.