A hybrid implementation of Hamming weight

The hamming weight (also known as population count) of a bitstring is the number of 1´s in the bitstring. It has applications in scopes like cryptography, chemical informatics and information theory. Typical bitstring lengths range from the processor´s word length to several thousands of bits. A plethora of hamming weight algorithms have been pro- posed. While some implementations expose just scalar par- allelism, others expose vector parallelism. Moreover, some implementations use special machine instructions that compute the hamming weight of a processor´s word. This paper presents a new hybrid scalar-vector hamming weight implementation that exposes both scalar and vector parallelism. This implementation will be useful on platforms that can exploit both kinds of parallelism simultaneously. On a Sandy Bridge platform, our hybrid implementation outperforms by up to 1.23X and 1.6X the, to the best of our knowledge, best scalar and vector implementations respectively.