3

I was asked this question in an interview and still cannot figure out what it does. Can someone explain what it does and how it does it?

v = v - ((v >> 1) & (T)~(T)0/3);                           // temp
v = (v & (T)~(T)0/15*3) + ((v >> 2) & (T)~(T)0/15*3);      // temp
v = (v + (v >> 4)) & (T)~(T)0/255*15;                      // temp
c = (T)(v * ((T)~(T)0/255)) >> (sizeof(T) - 1) * CHAR_BIT; // count
Matthew Hoggan
  • 7,402
  • 16
  • 75
  • 140

1 Answers1

10

It is explained here:

http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

Counting bits set, in parallel

A generalization of the best bit counting method to integers of bit-widths upto 128 (parameterized by type T) is this:

v = v - ((v >> 1) & (T)~(T)0/3);                           // temp
v = (v & (T)~(T)0/15*3) + ((v >> 2) & (T)~(T)0/15*3);      // temp
v = (v + (v >> 4)) & (T)~(T)0/255*15;                      // temp
c = (T)(v * ((T)~(T)0/255)) >> (sizeof(T) - 1) * CHAR_BIT; // count
ouah
  • 142,963
  • 15
  • 272
  • 331
  • Wow, that was fast! How did you find this? – templatetypedef Jun 14 '13 at 19:19
  • Just beat me to it! :D +1 for the fast find :) – Binayaka Chakraborty Jun 14 '13 at 19:20
  • 2
    @templatetypedef this page is THE page for C bit hacks, so I just went to check if it was already here. – ouah Jun 14 '13 at 19:21
  • @dtb in the page there is the explanation for the `32`-bit version, this version is a generalization and it is very similar to the `32`-bit version – ouah Jun 14 '13 at 19:23
  • @MatthewHoggan check the page for the explanation, you can find another explanation in this answer http://stackoverflow.com/questions/3815165/how-to-implement-bitcount-using-only-bitwise-operators – ouah Jun 14 '13 at 19:27
  • @ouah Thanks that second link explained it better. I googled the code, but did not understand the explaination. – Matthew Hoggan Jun 14 '13 at 19:30
  • It is basically the Hamming weight algorithm http://en.wikipedia.org/wiki/Hamming_weight – cup Jun 14 '13 at 22:46