高位比特 - 获取它们并将一个uint64_t转换为uint8_t

Question

假设您拥有一个uint64_t，只关心每个字节的高位比特。如下所示： uint32_t: 0000 ... 1000 0000 1000 0000 1000 0000 1000 0000 ---> 0000 1111

有比以下方法更快的方式吗？

   return
   (
     ((x >> 56) & 128)+
     ((x >> 49) &  64)+
     ((x >> 42) &  32)+
     ((x >> 35) &  16)+
     ((x >> 28) &   8)+
     ((x >> 21) &   4)+
     ((x >> 14) &   2)+
     ((x >>  7) &   1)
   )

Aka 移位、掩码和为每个字节添加正确的位？这将编译成很多汇编代码，我正在寻找更快的方法...我使用的机器只有 SSE2 指令，我没有找到有用的 SIMD 操作。感谢您的帮助。

- fission

---

你可以重新解释单个字节，循环遍历它们并屏蔽单个位。不知道这是否更快，但也许编译器可以更好地优化它。 - PlasmaHH

也许你可以先使用“0x8080808080808080”进行掩码处理，然后乘以特定的常数，将位放置在更方便的位置，以便在查找表中使用。 - R.. GitHub STOP HELPING ICE

你需要结果，也就是一个8位数的序列吗？或者只是检查HO位是否为“1”就足够了？ - nullpotent

是的，pmovmskb正好可以实现你想要的功能。如果我没记错，AVX2中会有一条整型指令也可以用来实现相同的操作（收集位，忘记助记符了）。 - harold

@AndyRoss 我正在编写它，花了一些时间，因为我真的想把那个新指令放进去 :) - harold

Answer 1

正如我在评论中提到的那样，pmovmskb 可以完成你需要的功能。以下是如何使用它：

MMX + SSE1:

movq mm0, input ; input can be r/m
pmovmskb output, mm0 ; output must be r

SSE2：

movq xmm0, input
pmovmskb output, xmm0

我查了一下新的方法

BMI2:

mov rax, 0x8080808080808080
pext output, input, rax ; input must be r

- harold

---

如果您添加了正确的内联汇编（带有适当的约束条件），以使用此方法生成最佳代码，则加1。 - R.. GitHub STOP HELPING ICE

@R.. 我想帮你，但我从来没有做过那个。我尽量避免接触 GCC。我看了一下那些限制条件，嗯，也许那段代码会在一段时间内出现... 也许。 - harold

好的，无论如何加1。如果我有时间研究如何做到这一点，我会添加它。 - R.. GitHub STOP HELPING ICE

这个汇编没有简单的内在函数吗？ - rubenvb

@rubenvb 你告诉我吧。我从来没搞清楚怎么使用内部函数从寄存器中进行 MOVQ。 - harold

Answer 2

return ((x & 0x8080808080808080) * 0x2040810204081) >> 56;

这个方法起作用了。&符号选择你想要保留的位。乘法将所有的位相乘，得到最高有效字节，并且移位将它们移到最低有效字节。由于大多数现代CPU上乘法很快，所以这种方法不应该比使用汇编慢太多。

- James

---

这实际上可能比pmovmsk更快，而我记得它是一个相当慢的指令。 - Gunther Piez

@drhirsch 2个时钟周期延迟（在AMD K10上为3个）和Core2的吞吐量为1，这并不算太糟糕...即使仅仅是这里的乘法也更差。 - harold

对于32位整数，常量为0x2204081，如下所示：return ((x & 0x80808080) * 0x2204081) >> 28; - Jack G

Answer 3

以下是使用SSE内嵌函数来完成的方法：

#include <xmmintrin.h>
#include <inttypes.h>
#include <stdio.h>

int main (void)
{
  uint64_t x
  = 0b0000000010000000000000001000000000000000100000000000000010000000;

  printf ("%x\n", _mm_movemask_pi8 ((__m64) x));
  return 0;
}

适用于以下情况：

gcc -msse

- ArjunShankar

Answer 4

不需要所有单独的逻辑AND，你可以简化为：

x &= 0x8080808080808080;
return (x >>  7) | (x >> 14) | (x >> 21) | (x >> 28) |
       (x >> 35) | (x >> 42) | (x >> 49) | (x >> 56);

(假设函数返回类型是uint8_t）。

您还可以将其转换为展开的循环：

uint8_t r = 0;

x &= 0x8080808080808080;

x >>= 7; r |= x;
x >>= 7; r |= x;
x >>= 7; r |= x;
x >>= 7; r |= x;
x >>= 7; r |= x;
x >>= 7; r |= x;
x >>= 7; r |= x;
x >>= 7; r |= x;
return r;

我不确定哪个实际表现更好，尽管我倾向于押注第一个 - 第二个可能会产生更短的代码，但具有长依赖链。

- caf

---

百万美元的问题是：gcc -msse 是否为此代码生成 pmovmskb？ :) - R.. GitHub STOP HELPING ICE

你可能想将该常量标识为 ULL，这样编译器就不会试图对有符号值进行操作。 - Mark B

@MarkB：在C++11中不需要这样做。 - Mike Seymour

我非常确定ULL从未被需要。 - R.. GitHub STOP HELPING ICE

在C99中也没有必要 - 因为x是无符号的，即使常量是有符号的，它也会被提升为无符号的（即使常量的类型比uint64_t更宽）。 - caf

Answer 5

首先，您实际上不需要那么多操作。您可以同时对多个比特进行操作：

x = (x >> 7) & 0x0101010101010101; // 0x0101010101010101
x |= x >> 28;                      // 0x????????11111111
x |= x >> 14;                      // 0x????????????5555
x |= x >>  7;                      // 0x??????????????FF
return x & 0xFF;

一种替代方法是使用模运算进行侧向加法。首先要注意的是，x％n是基于n + 1的位数之和，因此如果n + 1是2 ^ k，则将添加k位组。如果您从上面的t =（x >> 7）＆0x0101010101010101开始，您想要对7位组进行求和，因此t％127将是解决方案。但是，t％127仅适用于结果最多为126。 0x8080808080808080及以上将会产生错误的结果。我尝试了一些更正措施，但都不容易实现。

尝试使用模运算将我们置于只有上一个算法的最后一步的情况下是可能的。我们想要保留两个最不重要的位，然后将其他位按14组进行求和。所以：

ull t = (x & 0x8080808080808080) >> 7;
ull u = (t & 3) | (((t>>2) % 0x3FFF) << 2);
return (u | (u>>7)) & 0xFF;

但是t>>2表示t/4，<<2表示乘以4。如果我们有(a%b)*c == (a*c%b*c)，那么(((t>>2) % 0x3FFF) << 2)就是(t & ~3) % 0xFFFC。但我们也知道，如果a+b%c小于c，则a+b%c = (a+b)%c。所以我们只需要u = t % FFFC。得到：

ull t = ((x & 0x8080808080808080) >> 7) % 0xFFFC;
return (t | (t>>7)) & 0xFF;

- AProgrammer

Answer 6

这似乎有效：

return (x & 0x8080808080808080) % 127;

- dpi

---

如果第一位被设置了，因此需要一个大于等于128的答案。 - AProgrammer