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) --
loading...
Last Post: How to Validate Binary Search Tree in C/C++?
Next Post: How to Convert Roman to Integer in C/C++ and Python?
Another one, with constant complexity and “no loop”:
int count_group(uint32_t val)
{
static int bitcnt[] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 };
return bitcnt[val & 0xF] +
bitcnt[(val >> 4) & 0x0F ] +
bitcnt[(val >> 8) & 0x0F] +
bitcnt[(val >> 12) & 0x0F] +
bitcnt[(val >> 16) & 0x0F] +
bitcnt[(val >> 20) & 0x0F] +
bitcnt[(val >> 24) & 0x0F] +
bitcnt[(val >> 28) & 0x0F];
}
Another bit tweak
Wanted to mention that builtin popcount is actually calling POPCNT instruction of x86 machine.
Thanks! so it is not available on ARM?