将屏蔽位移至 lsb
Shift masked bits to the lsb
当您 and 一些带有掩码的数据时，您会得到一些与 data/mask 大小相同的结果。
我想做的是，将结果中的掩码位（掩码中有 1 的地方）移到右边，使它们彼此相邻，然后我可以对它们执行 CTZ（计数尾随零） .
我不知道如何命名这样的程序，所以 Google 让我失望了。该操作最好不是循环解决方案，这必须尽可能快地操作。
这是一张用 MS Paint 制作的令人难以置信的图像。
此操作被称为 compress right. It is implemented as part of BMI2 作为 PEXT 指令，在 Intel 处理器中自 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;
}
当然这些都可以通过展开变成"not a loop"，第二种和第三种方式可能更适合。然而，这有点作弊。
您可以使用与 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 位有一些重叠，所以我将它们分成两部分，第一个提取位 a 和 c，然后e和h将在后面提取。还有其他拆分位的方法，比如 a & h 然后 c & e。可以看到对比Harold函数的结果live on ideone
只有一次乘法的替代方法
const uint32_t X = (x << 8) | x;
return (X & 0x8821)*0x12050000 >> 28;
我通过复制位来得到这个，这样它们 spaced 更远，留下足够的 space 来避免进位。这通常比拆分成 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
相关：
- How to create a byte out of 8 bool values (and vice versa)?
- Redistribute least significant bits from a 4-byte array to a nibble
当您 and 一些带有掩码的数据时，您会得到一些与 data/mask 大小相同的结果。
我想做的是，将结果中的掩码位（掩码中有 1 的地方）移到右边，使它们彼此相邻，然后我可以对它们执行 CTZ（计数尾随零） .
我不知道如何命名这样的程序，所以 Google 让我失望了。该操作最好不是循环解决方案，这必须尽可能快地操作。
这是一张用 MS Paint 制作的令人难以置信的图像。
此操作被称为 compress right. It is implemented as part of BMI2 作为 PEXT 指令，在 Intel 处理器中自 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;
}
当然这些都可以通过展开变成"not a loop"，第二种和第三种方式可能更适合。然而，这有点作弊。
您可以使用与 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 位有一些重叠，所以我将它们分成两部分，第一个提取位 a 和 c，然后e和h将在后面提取。还有其他拆分位的方法，比如 a & h 然后 c & e。可以看到对比Harold函数的结果live on ideone
只有一次乘法的替代方法
const uint32_t X = (x << 8) | x;
return (X & 0x8821)*0x12050000 >> 28;
我通过复制位来得到这个，这样它们 spaced 更远，留下足够的 space 来避免进位。这通常比拆分成 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
相关：
- How to create a byte out of 8 bool values (and vice versa)?
- Redistribute least significant bits from a 4-byte array to a nibble