将掩码位移至最低有效位 (LSB)

Question

当你使用掩码对数据进行and运算时，你会得到与数据/掩码相同大小的结果。我想做的是将结果中被掩码为1的位向右移动，使它们相邻，并且可以对它们执行CTZ（Count Trailing Zeroes）操作。

我不知道如何命名这样的过程，所以谷歌无法帮助我。这个操作最好不要用循环来解决，必须尽可能快地完成此操作。

以下是在MS Paint中制作的令人难以置信的图像。

- cen

---

如果掩码不是恒定的，您需要使用循环。 - Gyapti Jain

掩码是常数，但有512个，所以并非真正的“常数”。 - cen

Answer 1

这个操作被称为compress right。它作为BMI2的一部分实现，被Intel Haswell处理器作为PEXT指令实现。

不幸的是，如果没有硬件支持，这将是一个相当麻烦的操作。当然，有一个显而易见的解决方案，就是在循环中逐位移动比特，以下是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; 
}

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

- harold

---

原来我的问题需要将位从高到低压缩一半的时间。因此，最高位在最低槽上打包，然后向下移动。是否有这个算法的版本可以做到这一点？反转数据和掩码可以实现这一点，但我认为这是一个代价太高的操作。 - cen

@cen，你可以使用蝴蝶网络和掩码来进行提取/翻转，该网站上的其他链接已经解释了这个过程。不过，也许只是进行反向提取更容易，反转并不会造成太大的影响，例如参见https://dev59.com/v2ox5IYBdhLWcg3wi0vF#9144870 - harold

如果结果需要被反转，那么可能我的建议的方式更好，而无需硬件支持。位操作技巧也使用类似这样的乘法来反转字节中的位。 - phuclv

Answer 2

您可以使用类似于这里描述的乘法打包技术。这样，您就不需要任何循环，并且可以以任何顺序混合位。

例如，对于像上面的掩码0b10101001 == 0xA9和8位数据abcdefgh（其中a-h是8位），您可以使用下面的表达式来获取0000aceh。

uint8_t compress_maskA9(uint8_t x)
{
    const uint8_t mask1 = 0xA9 & 0xF0;
    const uint8_t mask2 = 0xA9 & 0x0F;
    return (((x & mask1)*0x03000000 >> 28) & 0x0C) | ((x & mask2)*0x50000000 >> 30);
}

在这种特定情况下，在乘法步骤中添加时存在4位的重叠（会导致意外进位），因此我将它们分成了两部分，第一部分提取了位a和c，然后后面的部分将提取e和h。也有其他分割位的方法，比如 a & h 然后 c & e。您可以看到与 Harold 的函数的结果进行比较 在 ideone 上实时查看。

另一种只有一个乘法的替代方法。

const uint32_t X = (x << 8) | x;
return (X & 0x8821)*0x12050000 >> 28;

我通过复制比特，使它们间隔更远，留出足够的空间以避免进位得到了这个结果。这常常比拆分成两个乘法更好。

---

如果你想要结果的位数反转（即heca0000），你可以轻松地相应更改这些神奇数字。

// result: he00 | 00ca;
return (((x & 0x09)*0x88000000 >> 28) & 0x0C) | (((x & 0xA0)*0x04800000) >> 30);

或者您也可以同时提取3个位e、c和a，将h单独留下（正如我上面所提到的，通常会有多个解决方案），这样您只需要进行一次乘法。

return ((x & 0xA8)*0x12400000 >> 29) | (x & 0x01) << 3; // result: 0eca | h000

但是可能有更好的选择，就像上面的第二个片段一样。

const uint32_t X = (x << 8) | x;
return (X & 0x2881)*0x80290000 >> 28

正确性检查: http://ideone.com/PYUkty

对于更多的掩码，您可以预先计算与这些掩码对应的魔数，并将它们存储在数组中，以便您可以立即查找并使用它们。我手动计算了这些掩码，但您也可以自动执行此操作。

---

解释

我们有 abcdefgh & mask1 = a0c00000。将其与 magic1 相乘。

    ........................a0c00000
 ×  00000011000000000000000000000000 (magic1 = 0x03000000)
    ────────────────────────────────
    a0c00000........................
 + a0c00000......................... (the leading "a" bit is outside int's range
    ────────────────────────────────  so it'll be truncated)
r1 = acc.............................

=> (r1 >> 28) & 0x0C = 0000ac00

同样地，我们使用魔数magic2将abcdefgh & mask2 = 0000e00h相乘。

  ........................0000e00h
× 01010000000000000000000000000000 (magic2 = 0x50000000)
  ────────────────────────────────
  e00h............................
+ 0h..............................
  ────────────────────────────────
r2 = eh..............................

=> (r2 >> 30) = 000000eh

将它们结合在一起，我们就得到了预期的结果。

((r1 >> 28) & 0x0C) | (r2 >> 30) = 0000aceh

这是第二个片段的演示。

                  abcdefghabcdefgh
&                 1000100000100001 (0x8821)
  ────────────────────────────────
                  a000e00000c0000h
× 00010010000001010000000000000000 (0x12050000)
  ────────────────────────────────
  000h
  00e00000c0000h
+ 0c0000h
  a000e00000c0000h
  ────────────────────────────────
= acehe0h0c0c00h0h
& 11110000000000000000000000000000
  ────────────────────────────────
= aceh

针对倒序情况：

                  abcdefghabcdefgh
&                 0010100010000001 (0x2881)
  ────────────────────────────────
                  00c0e000a000000h
x 10000000001010010000000000000000 (0x80290000)
  ────────────────────────────────
  000a000000h
  00c0e000a000000h
+ 0e000a000000h
  h
  ────────────────────────────────
  hecaea00a0h0h00h
& 11110000000000000000000000000000
  ────────────────────────────────
= heca

相关：

• 如何将8个布尔值创建为一个字节（反之亦然）？
• 将4字节数组的最低有效位重新分配到半字节中

- phuclv

---

你如何计算乘数？ - harold

@harold 我只是将二进制乘法写出来，并在我想要将被乘数移位的魔术数字中打开位。例如，要将最低有效位移位到位28，我将位28设置为1。这里是使用您的函数进行的更正检查http://ideone.com/bud3dI - phuclv

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - phuclv