3 ms·
Quickest way (without multiplication) is divide and conquer, just like the usual bit popcount: static inline int f(const u64 m) { const u64 ones = 0x01
by pbsd 15y ago
Quickest way (without multiplication) is divide and conquer, just like the usual bit popcount:
static inline int f(const u64 m)
{
const u64 ones = 0x0101010101010101ULL;
const u64 b64 = m & ones;
const u32 b32 = b64 + (b64>>32);
const u16 b16 = b32 + (b32>>16);
const u8 b8 = b16 + (b16>> 8);
return b8;
}
- _sh 15y agoBut this is slower than with multiplication, as Linus explains: the simple shift+add version is all totally serialized and nothing can be done before the previous operation ends: as a result the three adds and three shifts will inevitably take 6 cycles (the original P4 had that double-pumped ALU, but not for shifts). That's already slower than almost any multiply. Edit: oops, I forgot your '(without multiplication)' qualifier. Yes, your way is likely the quickest without multiplication.