peltorator

Fast popcount

Apr 17th, 2021 (edited)
110
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. unsigned int bitcount32(uint32_t i) {                                                                                                              
  2.   i = i - ((i >> 1) & 0x55555555);
  3.   i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
  4.   return (((i + (i >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
  5.  
  6. }
  7.  
  8. unsigned int popcount64(unsigned long long x) {
  9.     x = (x & 0x5555555555555555ULL) + ((x >> 1) & 0x5555555555555555ULL);
  10.     x = (x & 0x3333333333333333ULL) + ((x >> 2) & 0x3333333333333333ULL);
  11.     x = (x & 0x0F0F0F0F0F0F0F0FULL) + ((x >> 4) & 0x0F0F0F0F0F0F0F0FULL);
  12.     return (x * 0x0101010101010101ULL) >> 56;
  13. }
RAW Paste Data