将屏蔽位移到lsb

Question

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

我不知道如何命名这样的程序,所以谷歌让我失望.该操作最好不应该是循环解决方案,这必须尽可能快地操作.

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

Answer 1

此操作称为压缩权限.它是作为的一部分BMI2为PEXT指导,以英特尔处理器为Haswell的的.

不幸的是,没有硬件支持是一个非常烦人的操作.当然有一个明显的解决方案,只需在循环中逐个移动位,这是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; 
}

当然,所有这些都可以通过展开变成"非循环",第二种和第三种方式可能更适合于此.然而,这有点作弊.