c++ - 将屏蔽位移至 lsb

Question

当你和一些带有掩码的数据时，你会得到一些与数据/掩码大小相同的结果。我想要做的是获取结果中的掩码位(掩码中有 1)并将它们向右移动，以便它们彼此相邻，我可以对它们执行 CTZ(计数尾随零) .

我不知道如何命名这样的程序，所以 Google 让我失望了。该操作最好不是循环解决方案，这必须是尽可能快的操作。

这是一张用 MS Paint 制作的令人难以置信的图像。

Answer 1

此操作称为 compress right .它是作为 BMI2 的一部分实现的。作为 PEXT 指令，在从 Haswell 开始的 Intel 处理器中。

不幸的是，如果没有硬件支持，这是一个非常烦人的操作。当然有一个明显的解决方案，就是在循环中逐个移动位，这里是 Hackers Delight 给出的:

unsigned compress(unsigned x, unsigned m) {
   unsigned r, s, b;    // Result, shift, mask bit. 

   r = 0; 
   s = 0; 
   do {
      b = m & 1; 
      r = r | ((x & b) << s); 
      s = s + b; 
      x = x >> 1; 
      m = m >> 1; 
   } while (m != 0); 
   return r; 
} 

但是还有另一种方式，同样由 Hackers Delight 给出，它执行的循环次数更少(迭代次数与比特数成对数)，但每次迭代次数更多:

unsigned compress(unsigned x, unsigned m) {
   unsigned mk, mp, mv, t; 
   int i; 

   x = x & m;           // Clear irrelevant bits. 
   mk = ~m << 1;        // We will count 0's to right. 

   for (i = 0; i < 5; i++) {
      mp = mk ^ (mk << 1);             // Parallel prefix. 
      mp = mp ^ (mp << 2); 
      mp = mp ^ (mp << 4); 
      mp = mp ^ (mp << 8); 
      mp = mp ^ (mp << 16); 
      mv = mp & m;                     // Bits to move. 
      m = m ^ mv | (mv >> (1 << i));   // Compress m. 
      t = x & mv; 
      x = x ^ t | (t >> (1 << i));     // Compress x. 
      mk = mk & ~mp; 
   } 
   return x; 
}

请注意，那里的许多值仅取决于 m。由于您只有 512 个不同的掩码，您可以预先计算这些掩码并将代码简化为类似这样的内容(未经测试)

unsigned compress(unsigned x, int maskindex) {
   unsigned t; 
   int i; 

   x = x & masks[maskindex][0];

   for (i = 0; i < 5; i++) {
      t = x & masks[maskindex][i + 1]; 
      x = x ^ t | (t >> (1 << i));
   } 
   return x; 
}

当然，所有这些都可以通过展开变成“非循环”，第二种和第三种方式可能更适合这种情况。不过，这有点作弊。