algorithm - 从 ulong 中删除位的快速方法

Question

我想从 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) .

Answer 1

这被称为 compress right 。不幸的是，如果没有特殊的硬件支持(以 pext 的形式存在，相当新)，就没有真正的好方法来做到这一点。以下是 Hackers Delight 中给出的一些方法，已修改为 C# 和 64 位 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; 
}