algorithm - 计算无符号 64 位整数中零半字节的数量

Question

例如，0x1230560181feab00 有 4 个零半字节，0x00000123456780ab 有 6 个。我如何在不进行简单循环和计数的情况下快速计算它？有什么很酷的技巧吗？

Answer 1

是的，首先“收集整个半字节的零”(所有 4 位的或):

x |= x >> 1;
x |= x >> 2;

删除垃圾:

x &= 0x1111111111111111UL;

然后只要popcnt你想要的任何方式，如果你有可用的说明那太好了。当然，这给出了不为零的半字节数，但这是相同的信息，只需从 16 中减去即可。

如果您打算使用回退，其中一些可以进行优化，因为您知道每个半字节都是 0 或 1，因此例如在以 ulong result = value - ( (value >> 1) & 0x5555555555555555UL);，可以跳过两个缩减阶段。

所以你可以使用这个:

x = (x + (x >> 4)) & 0xF0F0F0F0F0F0F0FUL;
count = (x * 0x101010101010101UL) >> 56

做最后的计数。

不幸的是，尝试使用那里的半字节很小，因此尝试仅使用不同的乘数来删除倒数第二个缩减步骤 just 是行不通的 - 最后的总和可能是 16但是使用 (x * 0x1111111111111111UL) >> 60 不能得到 16。