Premium
A bit‐counting algorithm using the frequency division principle
Author(s) -
Berkovich Simon,
Lapir Gennadi M.,
Mack Marilyn
Publication year - 2000
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/1097-024x(20001125)30:14<1531::aid-spe347>3.0.co;2-a
Subject(s) - bitwise operation , computer science , arithmetic , division (mathematics) , bit (key) , binary number , set (abstract data type) , algorithm , 8 bit , table (database) , word (group theory) , point (geometry) , theoretical computer science , computer hardware , mathematics , programming language , data mining , geometry , computer security
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.