-synx-'s blog

Counting bits in unsigned 64 bit using precomputation?
By -synx-, history, 9 years ago, In English

I know that counting bits using precomputation is the fastest way to go (over __builtin_popcount()).
For 32 bit integers we can do cnt[x>>16]+cnt[x&65535] by precomputing counts upto (1<<16).
How can we do it for 64 bit integers by precomputing upto (1<<22).

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
9 years ago, hide # |
 
Vote: I like it +15 Vote: I do not like it

I don't understand, why can't we just do cnt[(x>>48)&65535]+cnt[(x>>32)&65535]+cnt[(x>>16)&65535]+cnt[x&65535]? or is this too slow? If we precompute upto (1<<22) then it would be cnt[(x>>44)&4194303]+cnt[(x>>22)&4194303]+cnt[x&4194303]. Though, I don't know if this is the fastest way.

→ Reply