A Faster Approach to Count Set Bits in a 32-bit Integer

A bit is set if it is ‘1’. To count how many ‘set’ bits in a 32-bit integer (signed or unsigned), we can use the following straightforward method:

1
2
3
4
5
6
7
8

inline int bitCount1(int i) {
    int count = 0;
    for (int j = 0; j < 32; j ++) {
        if (i < 0) count ++;
        i <<= 1;
    }
    return count;
}

inline int bitCount1(int i) {
    int count = 0;
    for (int j = 0; j < 32; j ++) {
        if (i < 0) count ++;
        i <<= 1;
    }
    return count;
}

By shifting one position each time to the left, if the number becomes negative (the left-most bit, significant bit), we have a bit set. This approach needs to check 32 times (but can be easily adapted to 64-bit integer).

We can use binary logics to remove the loop, which is a lot faster.

1
2
3
4
5
6
7
8

inline int bitCount2(int i) {
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    i = (i + (i >> 4)) & 0x0f0f0f0f;
    i = i + (i >> 8);
    i = i + (i >> 16);
    return i & 0x3f;
}

inline int bitCount2(int i) {
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    i = (i + (i >> 4)) & 0x0f0f0f0f;
    i = i + (i >> 8);
    i = i + (i >> 16);
    return i & 0x3f;
}

The first line counts the number of ones every two bits and store them using two bits. For example, 01101100 -> 01011000. The original can be grouped to 01 10 11 00, the number of ones is 1, 1, 2, 0 then written in binary is 01011000.

The second counts the number of ones every four bits and store them using four bits. The number we obtained after the first operation is 01011000, then we group them into 0101, 1000 and add neighbour two bits, 01+01=10, 10+00=10, and represent them using four bits, which is 0010 0010.

And this goes on every 8, 16, 32 bits.

The rough performance comparison is done using GNU C++ compiler (RELEASE mode), the first naive approach is about 60 times slower than the second bit method.

–EOF (Coding For Speed) —