Population count of a bitset is defined as number of bits set to 1.
The most obvious approach would be to scan every bit and check for its status and maintain a counter for the set bits -
This code runs in O(k) where k is the number of bits. It can be little better by replacing the (i < 64) condition by (b!=0) to stop when b no longer has any set bits.
A better approach suggested by Brian Kernighan was to keep resetting LS1B (Lease Significant 1 Bit) until the bitset becomes 0.
We can reset the LS1B in O(1) which means this algorithm runs in O(r) where r is the number is set bits.
Another approach is to use pre-calculated lookup tables. For n bit long bitset, there are 2^n possible numbers that can be generated using them. If we pre-calculate the population count for the entire set of 2^64 numbers, it will pollute the cache and besides it won't be memory efficient. But we can use Divide and Conquer to create 8 groups of 8 bits each. And for each group of 8 bits, there are 2^8=256 possible numbers for which we can easily generate a pre-calculated lookup table. We can do this as - Now all we need is to get groups of 8 bits in the LS8B (Lease Significant 8 Bit) positions of the bit set (while the top (MSB) 56 bits are all reset) and then find its popcnt by using the lookup table as - Note:
The most obvious approach would be to scan every bit and check for its status and maintain a counter for the set bits -
This code runs in O(k) where k is the number of bits. It can be little better by replacing the (i < 64) condition by (b!=0) to stop when b no longer has any set bits.
A better approach suggested by Brian Kernighan was to keep resetting LS1B (Lease Significant 1 Bit) until the bitset becomes 0.
We can reset the LS1B in O(1) which means this algorithm runs in O(r) where r is the number is set bits.
Another approach is to use pre-calculated lookup tables. For n bit long bitset, there are 2^n possible numbers that can be generated using them. If we pre-calculate the population count for the entire set of 2^64 numbers, it will pollute the cache and besides it won't be memory efficient. But we can use Divide and Conquer to create 8 groups of 8 bits each. And for each group of 8 bits, there are 2^8=256 possible numbers for which we can easily generate a pre-calculated lookup table. We can do this as - Now all we need is to get groups of 8 bits in the LS8B (Lease Significant 8 Bit) positions of the bit set (while the top (MSB) 56 bits are all reset) and then find its popcnt by using the lookup table as - Note:
