创建新蒙版

Question

我正在寻找一种最佳方法，该方法将基于 ulong 列表，查看 4 位对，如果这些位中的任何一个设置为 1，则应该将新 ulong 值中的第一位设置为 1否则为 0。

例如

列表 qwords = new List() {0x1, 0x1, 0x1} ulong myMask = 0;

现在依次检查每个 qword 的所有 4 位对，我们应该得到以下值。

新值：0001 0000 0000 0000 0001 0000 0000 0000 0001

我的掩码 = 4295032833(0x100010001)

列表中给出的示例只是为了更容易理解代码逻辑是如何工作的。 谁能帮助我如何最佳地解决这个问题？

Answer 1

据我了解这个问题，我们计算每个半字节是否设置了任何位，然后我们“压缩”它以获得一个掩码，指示哪个半字节至少有一个设置位。

第一步很简单：

for (int i = 0; i < qwords.Length; i++)
{
    ulong bits = qwords[i];
    bits |= bits >> 1;
    bits |= bits >> 2;
    qwords[i] = bits;
}

我正在此处修改原始列表，但当然欢迎您将中间结果放在其他地方。

然后，如果我们被允许使用 System.Runtime.Intrinsics.X86 并且支持 BMI2，我们可以像这样进行“压缩”（对于 4 个 qword 的列表）：

ulong m = 0x1111111111111111;
ulong myMask = Bmi2.X64.ParallelBitExtract(qwords[0], m) |
    (Bmi2.X64.ParallelBitExtract(qwords[1], m) << 16) |
    (Bmi2.X64.ParallelBitExtract(qwords[2], m) << 32) |
    (Bmi2.X64.ParallelBitExtract(qwords[3], m) << 48);

否则，使用方法

compress

（下文进一步介绍）我们可以做到这一点：

ulong myMask = compress(qwords[0]) |
    (compress(qwords[1]) << 16) |
    (compress(qwords[2]) << 32) |
    (compress(qwords[3]) << 48);

我们可以像这样

compress

：

ulong compress(ulong x)
{
    x = (x & 0x0101010101010101) | ((x & 0x1010101010101010) >> 3);
    x = (x & 0x0003000300030003) | ((x & 0x0300030003000300) >> 6);
    x = (x & 0x0000000F0000000F) | ((x & 0x000F0000000F0000) >> 12);
    x = (x & 0x00000000000000FF) | ((x & 0x000000FF00000000) >> 24);
    return x;
}

对于最多 4 个 qword 的列表：

ulong myMask = 0;
for (int i = 0; i < qwords.Length; i++)
{
    ulong bits = qwords[i];
    bits |= bits >> 1;
    bits |= bits >> 2;
    myMask |= compress(bits) << (i * 16);
}