Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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;
  }


But 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.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: