Count Set Bits using Lookup Table

Given an integer, count set bits in it.


 
For example,


Input:  n = -1 (11..1111)
Output: The number of set bits in -1 is 32

Input:  n = 16 (00001000)
Output: The number of set bits in 16 is 1

 


 
We have discussed a naive solution and Brian Kernighan’s algorithm to count number of set bits in a number in previous post. Both have worst case time complexity of O(log(n)). In this post, a O(1) time solution is discussed.
 

The idea is to use a lookup table to return number of set bits in a number in constant time. An integer in C/C++ usually takes 4 bytes for storage. That means maximum number it can store is 232 – 1. A lookup table for all 232 – 1 integers will be infeasible (Not to forget, we have negative numbers too). The trick is to create an 8-bit (1 byte) version of the table, then iterate over each byte in the integer to be checked and summing the results of the table lookup.

1 byte with all its bits set is 255 in decimal (11111111 in binary) and all bits unset is 0 in decimal (00000000 in binary). So lookup table should be of size 256 (0-255).
 

In the solution below, we’re using the macros to generate the lookup table. The lookup table will be generated at compile time by preprocessor. The first and last few numbers of the sequence will be
{ 0, 1, 1, 2, 1, . . . , 7, 6, 7, 7, 8 } as

0 has 0 bits
1 has 1 bits
2 has 1 bits
3 has 2 bits
4 has 1 bits
..
..
251 has 7 bits
252 has 6 bits
253 has 7 bits
254 has 7 bits
255 has 8 bits

 
C++ implementation –
 

Download   Run Code

Output:

-1 in binary is 11111111111111111111111111111111
The number of set bits in -1 is 32

 
References: https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz