c - C 中的 Bit Hack 无法理解

Question

我在一次采访中被问到这个问题，但仍然无法弄清楚它的作用。有人可以解释它的作用以及它是如何做的吗？

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

Answer 1

这里解释：

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

计数位设置，并行

将最佳位计数方法推广到位宽高达 128 的整数（由类型 T 参数化）是这样的：

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