使用掩码对某些数据进行and时，会得到一些与数据/掩码大小相同的结果。我想要做的是取结果中的掩码位（掩码中有1）并将它们向右移动，使它们彼此相邻，我可以对它们执行CTZ（计数尾随零） 。
我不知道如何命名这样的程序，所以谷歌让我失望。该操作最好不应该是循环解决方案，这必须尽可能快地操作。
这是一个用MS Paint制作的令人难以置信的图像。
此操作称为compress right。它作为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;
}
当然，所有这些都可以通过展开变成“非循环”，第二种和第三种方式可能更适合于此。然而，这有点作弊。
您可以使用与here描述的类似的逐个乘法技术。这样您就不需要任何循环，并且可以按任何顺序混合位。
例如，使用上面的掩码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位重叠（这会导致意外的进位），所以我将它们分成2部分，第一部分提取比特a和c，然后e和h将是在后一部分提取。还有其他方法可以分割比特，比如a＆h然后c＆e。您可以看到与Harold的函数live on ideone相比较的结果
另一种只有一次乘法的方法
const uint32_t X = (x << 8) | x;
return (X & 0x8821)*0x12050000 >> 28;
我通过复制这些位使得它们间隔得更远，留下足够的空间来避免携带。这通常比分成2次乘法更好
如果您希望结果的位反转（即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
对于大量的掩码，您可以预先计算与这些掩码相对应的幻数，并将它们存储在一个数组中，以便您可以立即查找它们以供使用。我手工计算了这些面具，但你可以do that automatically
我们有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
同样地，我们将abcdefgh & mask2 = 0000e00h与magic2相乘
........................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