CODEWITHSUNDEEP
cbit-manipulation
Matthew Hoggan
Matthew Hoggan

Reputation: 7594

Bit Hack in C Cannot Understand

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

Upvotes: 3

Views: 474

Answers (1)

ouah
ouah

Reputation: 145829

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

Upvotes: 10

Related Questions