将屏蔽位移到lsb

当你and一些带掩码的数据得到一些与数据/掩码大小相同的结果时。 我想要做的是取结果中的掩码位（掩码中有1）并将它们向右移动，使它们彼此相邻，我可以在它们上执行CTZ（计数尾随零） 。

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

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

Answer 1

此操作称为压缩权限 。 它作为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; } 

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

Answer 2

您可以使用类似于此处描述的逐个乘法技术。 这样你就不需要任何循环了。

例如，如上面的掩码0b10101001 == 0xA9和8位数据abcdefgh （啊是8位）你可以使用下面的表达式得到0000aceh

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

在这种情况下，当乘法时有4位的一些重叠，所以我将它们分成2部分，第一部分提取比特a和c，然后e和h将在后一部分被提取。

你可以看到它的结果与Harold 在ideone上的function相比较

如果您希望结果的位反转，您可以轻松地相应地更改幻数。

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

或者您可以同时提取3位e，c和a，由于某些重叠位而单独留下h：

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

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

对于大量掩码，您可以预先计算与该掩码对应的幻数，并将它们存储到数组中供以后使用。

---

说明

我们有abcdefgh & mask1 = a0c00000

  ........................a0c00000 x 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 

同样abcdefgh & mask2 = 0000e00h

  ........................0000e00h x 01010000000000000000000000000000 (magic2 = 0x50000000) __________________________________________________________________ 0000e00h............................ + 0000e00h.............................. ↓↓ __________________________________________________________________ r2 = eh.............................. => (r2 >> 30) = 000000eh 

因此

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