How to count the number of the bits in the long long type variables?

Question

I want to count the bits in the long long type variable. For example, 1100011001 -> 5

In the integer type, I can use

a = (a & 0x5555) + ((a & 0xAAAA) >> 1); 
a = (a & 0x3333) + ((a & 0xCCCC) >> 2); 
a = (a & 0x0F0F) + ((a & 0xF0F0) >> 4); 
a = (a & 0x00FF) + ((a & 0xFF00) >> 8);

but in case of "long long", how to do that?

`__builtin_popcountll()` if you're using gcc or clang. Probably doesn't count if this is for homework, of course. — Shawn, Apr 20 '19 at 13:17
If you understand *why* that works, it shouldn't be that hard to extend it to a wider integer type. — molbdnilo, Apr 20 '19 at 13:19
Or if using a even remotely recent x86 cpu, `_mm_popcnt_u64()` from ``. Same caveat. — Shawn, Apr 20 '19 at 13:23
Or there's always good old `std::bitset<64> b{yournumber}; auto numbits = b.count();` — Shawn, Apr 20 '19 at 13:27

score 1 · Accepted Answer · answered Apr 20 '19 at 13:23

Your code is for 16-bit integers.

To make it work with 32-bit integers, you need to:

make each literal in it two times wider (while preserving the pattern),
add one more line of code.

Here's the result:

a = (a & 0x55555555) + ((a & 0xAAAAAAAA) >> 1); 
a = (a & 0x33333333) + ((a & 0xCCCCCCCC) >> 2); 
a = (a & 0x0F0F0F0F) + ((a & 0xF0F0F0F0) >> 4); 
a = (a & 0x00FF00FF) + ((a & 0xFF00FF00) >> 8); 
a = (a & 0x0000FFFF) + ((a & 0xFFFF0000) >> 16);

Then, to make it work with 64-bit integers, you repeat the same procedure:

a = (a & 0x5555555555555555) + ((a & 0xAAAAAAAAAAAAAAAA) >> 1); 
...
a = (a & 0x0000FFFF0000FFFF) + ((a & 0xFFFF0000FFFF0000) >> 16); 
a = (a & 0x00000000FFFFFFFF) + ((a & 0xFFFFFFFF00000000) >> 32);

How to count the number of the bits in the long long type variables?

1 Answers1