快速去除乌龙面的方法

小编典典

快速去除乌龙面的方法

algorithm

我想从64位字符串中删除位（以无符号长表示）。我可以通过一系列的掩码和移位操作来做到这一点，或者像下面的代码那样遍历每个位。是否有一些巧妙的位旋转方法来使执行速度更快？

public ulong RemoveBits(ulong input, ulong mask)
{
    ulong result = 0;
    ulong readbit = 1;
    ulong writebit =1;
    for (int i = 0; i < 64; i++)
    {   
        if ((mask & readbit) == 0) //0 in the mask means retain that bit
        {
            if ((input & readbit) > 0)
            {
                result+= writebit;  
            }
            writebit*=2;
        }
        readbit *= 2;
    }
    return result;
}

RemoveBits在性能至关重要的情况下，我需要执行数百万次。

它可能太抽象而无法提供帮助，但是虽然在编译时未知，但使用的不同掩码的数量是在运行时提早确定的（在性能至关重要的位之前），并且数量可能少于100。本质上，我正在使用代表的位串n-tuple，并RemoveBits投射到上m-tuple
(m < n)。

阅读 210

2020-07-28

共1个答案

小编典典

这称为压缩权。不幸的是，如果没有特殊的硬件支持（存在于pext，而是新的），没有什么好办法。以下是在Hackers
Delight中给出的一些方法，这些方法已修改为C＃和64bit ulong，但未经测试：

ulong compress(ulong x, ulong m) {
   ulong 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; 
}

这样的好处是分支比问题代码少得多。

还有一种方法，其循环迭代要少得多，但是步骤要复杂得多：

ulong compress(ulong x, ulong m) {
   ulong 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 < 6; i++) {
      mp = mk ^ (mk << 1);             // Parallel prefix. 
      mp = mp ^ (mp << 2); 
      mp = mp ^ (mp << 4); 
      mp = mp ^ (mp << 8); 
      mp = mp ^ (mp << 16); 
      mp = mp ^ (mp << 32);
      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; 
}

2020-07-28