Compute Number of 1’s Bits in C/C++

Write a function that takes an unsigned integer and returns the number of ’1′ bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11′ has binary representation 00000000000000000000000000001011, so the function should return 3.

The number of set bits in a binary string is also called the Hamming Weight, population count, popcount, or sideways sum.

This early post describes two method in getting the number of 1 bits.

Shifting Left and Test for Sign

We shift the integer 1 position left and add 1 to the answer if the integer becomes negative (the Most Significant Big denotes the sign for a signed integer). This is O(logN) complexity.

1
2
3
4
5
6
7
8

int hammingWeight(int i) {
    int r = 0;
    for (int j = 0; j < 32; j ++) {
        if (i < 0) r ++;
        i <<= 1;
    }
    return r;
}

int hammingWeight(int i) {
    int r = 0;
    for (int j = 0; j < 32; j ++) {
        if (i < 0) r ++;
        i <<= 1;
    }
    return r;
}

Bit Hacks

Many similar bit hacking approaches group pop counts in group of 2, 4, 8 .. bits one by one. No loops, the complexity is constant.

1
2
3
4
5
6

int hammingWeight(uint64_t x) {
    x -= (x >> 1) & 0x5555555555555555;             //put count of each 2 bits into those 2 bits
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333); //put count of each 4 bits into those 4 bits 
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f;        //put count of each 8 bits into those 8 bits 
    return (x * 0x0101010101010101) >> 56;  //returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ... 
}  

int hammingWeight(uint64_t x) {
    x -= (x >> 1) & 0x5555555555555555;             //put count of each 2 bits into those 2 bits
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333); //put count of each 4 bits into those 4 bits 
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f;        //put count of each 8 bits into those 8 bits 
    return (x * 0x0101010101010101) >> 56;  //returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ... 
}  

Recursion

Testing for the least-significant bit. We use n & 1 which is the same as n % 2 but more efficient/elegant. We use bit shifting n >> 1 instead of n /= 2 because it is faster.

1
2
3

int hammingWeight(uint32_t n) {
    return (n & 1) + (n == 0 ? 0 : hammingWeight(n >> 1));
}

int hammingWeight(uint32_t n) {
    return (n & 1) + (n == 0 ? 0 : hammingWeight(n >> 1));
}

Inbuilt Cheating

GCC Compilers provide inbuilt function to get the pop count.

1
2
3

int hammingWeight(uint32_t n) {
    return __builtin_popcount(n);
}

int hammingWeight(uint32_t n) {
    return __builtin_popcount(n);
}

This is shown just to avoid re-inventing the wheel.

n & (n - 1)

You use n & (n - 1) to remove the least-significant 1. So every time, we remove 1 until the number becomes zero.

1
2
3
4
5

int hammingWeight(uint32_t n) {
    int r = n ? 1 : 0;
    while (n &= (n - 1)) ++ r;
    return r;
}

int hammingWeight(uint32_t n) {
    int r = n ? 1 : 0;
    while (n &= (n - 1)) ++ r;
    return r;
}

Notice that this is on average faster than O(logN). Actually this is O(K) where K is the number of set bits for the integer.

Shifting to the right

We can shift 1 bit to the right and add the n & 1 (the LSB) to the answer.

1
2
3
4
5

int hammingWeight(uint32_t n) {
    int r = n & 1;
    while (n >>= 1) r += (n & 1);
    return r;
}

int hammingWeight(uint32_t n) {
    int r = n & 1;
    while (n >>= 1) r += (n & 1);
    return r;
}

Pre-calculated Caching

The other technique to speed up the process is to pre-computed the Hamming weight for 0 to 65535 (two bytes).

1
2
3
4
5

static uint8_t cache[65536] = { /* bitcounts of integers 0 through 65535, inclusive */ };
int hammingWeight(uint32_t i)
{
    return (cache[i & 0xFFFF] + cache[i >> 16]);
}

static uint8_t cache[65536] = { /* bitcounts of integers 0 through 65535, inclusive */ };
int hammingWeight(uint32_t i)
{
    return (cache[i & 0xFFFF] + cache[i >> 16]);
}

The result would be to sum up to 1 bits in two groups (high 16 bits and low 16 bits).

Hamming Weight / Hamming Distance Algorithms:

• A faster approach to count set bits in a 32-bit integer
• GoLang: Compute the Hamming Distance
• How to Sort List by Hamming Weight in C++?
• Teaching Kids Programming – Compute the Hamming Distance of Two Integers
• Compute the Total Hamming Distance between All Pairs of Integers
• The Hamming Distance Implementation in Javascript
• Hamming Distance between Two Integers
• Compute Number of 1's Bits in C/C++
• Teaching Kids Programming – Sort List by Hamming Weight

--EOF (The Ultimate Computing & Technology Blog) --