c - 复杂的c代码，我需要任何人来解释它是如何工作的？

Question

我有以下函数，女巫获取一个整数（十进制数）并在将其转换为二进制后返回该整数的个数，（例如，如果我们传递 6，该函数将返回 2，因为十进制的 6 等于二进制的 110） . 这很好，但不幸的是我无法理解它是如何工作的。代码是：

int number_of_ones(int i){
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

有没有人可以向我解释它是如何工作的？

Answer 1

这是一种无需分支即可计算设置为 1 的位数的算法。这里描述：

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