将 byte 中的每一位转换为 32 位 int 中每个半字节的第一位
Convert each bit in byte to first bit of each nibble in 32 bit int
我有一个字节b。我正在寻找最有效的位操作
将 b 中的每一位转换为 32 位 int x.
中每个半字节的第一位
例如，如果b = 01010111，则x = 0x10101111
我知道我可以使用蛮力方法：
x = (b&1) | (((b>>1)&1)<<4) | ......
编辑：这是用于 GPU 的 OpenCL 内核
PDEP
正如用户 harold 在评论中提到的那样，PDEP is the instruction that just does exactly what you want - but it's only available on x86 (as far as I know), and it has terrible1 performance on the newest AMD chips。
查找表
除此之外，查找 table 256 x 4 字节的条目似乎是合理的 - 代价是对缓存子系统造成 1K 的压力。你会发现很多聪明人反对 LUT，因为缓存未命中的隐藏成本 - 但如果这个特定操作实际上是 "hot" 那么即使考虑到任何额外的未命中，它也可能是最快的.
与任何 LUT 解决方案一样，您应该特别小心地对其进行基准测试，不仅要使用微基准，还要在整个应用程序中评估内存压力的影响。
您还可以考虑折衷的拆分 LUT 解决方案，该解决方案对字节的每个半字节使用一个或两个 16 条目 LUT，计算结果如下：
int32 x = high_lut[(b & 0xF0) >> 4] | low_lut[b & 0xF]
这将 LUT 的大小减少了约 11 到 322 之间的一个因子，因为我们的条目少得多，有些条目可以是 2 个字节而不是 4 个字节字节。
位操作
如果你真的想要一个位操作解决方案，打动你的姻亲什么的，你可以试试下面这样的东西：
- 将字节拆分为半字节并使用乘以
0x00001111（低半字节）和 0x01111000（高半字节）将低（resp.high）半字节拆分为低（resp high） 4 字节字的一半，并将结果与 or 或 add 组合。所以如果你的字节有位 abcd efgh 你就会有一个像 abcd abcd abcd abcd efgh efgh efgh efgh. 这样的词
and 这个结果带有一个掩码，可以挑选出属于每个半字节的位（尽管它通常不会在正确的位置）。掩码类似于 0x84218421，结果（二进制）类似于 a000 0b00 00c0 000d e000 0f00 00g0 000h.- 现在使用减法的进位行为将不在高位的 8 位中的 6 位移动到正确的位置，例如：
((x | 0x08880888) - 0x01110111) ^ 0x08880888.
最后一步的基本思想是设置每个半字节的高位，并从半字节减1。因此，例如，您有 0b00 半字节，它变成 1b00 - 1 - 减法包含所有零，并停在第一个，即高位（b 是零）或 b 如果它是一个。因此，您可以根据所选位的值有效地设置高位。请注意，您不需要为 a 或 e 执行此操作，因为它们已经在正确的位置。
需要最后的xor因为上面实际上是将高位设置为与选中位相反的值，所以需要翻转
我没试过，肯定有BUG，但基本思路应该没问题。可能有多种方法可以进一步优化它，但还不算太糟糕：几个乘法和可能六个位运算。在乘法速度较慢的平台上，您可能会为第一步找到另一种方法，它仅使用一次乘法结合一些更原始的操作，或者以更多操作为代价的零。
1 吞吐量比英特尔差整整 18 倍 - 显然 AMD 选择不在硬件中实现执行 PDEP 的电路，而是通过一系列更基本的操作来实现它。
2 最大的减少是如果您为高半字节和低半字节共享一个 16 条目 LUT，尽管这需要对高半字节的结果进行额外的移位抬头。示例中所示的较小缩减使用两个 16 条目 LUT：一个 4 字节的高半字节，一个 2 字节的低半字节，并避免了移位。
我有一个字节b。我正在寻找最有效的位操作
将 b 中的每一位转换为 32 位 int x.
例如，如果b = 01010111，则x = 0x10101111
我知道我可以使用蛮力方法：
x = (b&1) | (((b>>1)&1)<<4) | ......
编辑：这是用于 GPU 的 OpenCL 内核
PDEP
正如用户 harold 在评论中提到的那样，PDEP is the instruction that just does exactly what you want - but it's only available on x86 (as far as I know), and it has terrible1 performance on the newest AMD chips。
查找表
除此之外，查找 table 256 x 4 字节的条目似乎是合理的 - 代价是对缓存子系统造成 1K 的压力。你会发现很多聪明人反对 LUT，因为缓存未命中的隐藏成本 - 但如果这个特定操作实际上是 "hot" 那么即使考虑到任何额外的未命中，它也可能是最快的.
与任何 LUT 解决方案一样，您应该特别小心地对其进行基准测试，不仅要使用微基准，还要在整个应用程序中评估内存压力的影响。
您还可以考虑折衷的拆分 LUT 解决方案，该解决方案对字节的每个半字节使用一个或两个 16 条目 LUT，计算结果如下：
int32 x = high_lut[(b & 0xF0) >> 4] | low_lut[b & 0xF]
这将 LUT 的大小减少了约 11 到 322 之间的一个因子，因为我们的条目少得多，有些条目可以是 2 个字节而不是 4 个字节字节。
位操作
如果你真的想要一个位操作解决方案，打动你的姻亲什么的，你可以试试下面这样的东西：
- 将字节拆分为半字节并使用乘以
0x00001111（低半字节）和0x01111000（高半字节）将低（resp.high）半字节拆分为低（resp high） 4 字节字的一半，并将结果与or或add组合。所以如果你的字节有位abcd efgh你就会有一个像abcd abcd abcd abcd efgh efgh efgh efgh. 这样的词
and这个结果带有一个掩码，可以挑选出属于每个半字节的位（尽管它通常不会在正确的位置）。掩码类似于0x84218421，结果（二进制）类似于a000 0b00 00c0 000d e000 0f00 00g0 000h.- 现在使用减法的进位行为将不在高位的 8 位中的 6 位移动到正确的位置，例如：
((x | 0x08880888) - 0x01110111) ^ 0x08880888.
最后一步的基本思想是设置每个半字节的高位，并从半字节减1。因此，例如，您有 0b00 半字节，它变成 1b00 - 1 - 减法包含所有零，并停在第一个，即高位（b 是零）或 b 如果它是一个。因此，您可以根据所选位的值有效地设置高位。请注意，您不需要为 a 或 e 执行此操作，因为它们已经在正确的位置。
需要最后的xor因为上面实际上是将高位设置为与选中位相反的值，所以需要翻转
我没试过，肯定有BUG，但基本思路应该没问题。可能有多种方法可以进一步优化它，但还不算太糟糕：几个乘法和可能六个位运算。在乘法速度较慢的平台上，您可能会为第一步找到另一种方法，它仅使用一次乘法结合一些更原始的操作，或者以更多操作为代价的零。
1 吞吐量比英特尔差整整 18 倍 - 显然 AMD 选择不在硬件中实现执行 PDEP 的电路，而是通过一系列更基本的操作来实现它。
2 最大的减少是如果您为高半字节和低半字节共享一个 16 条目 LUT，尽管这需要对高半字节的结果进行额外的移位抬头。示例中所示的较小缩减使用两个 16 条目 LUT：一个 4 字节的高半字节，一个 2 字节的低半字节，并避免了移位。