求基于ulong列表生成掩码的最优方案：按4位组置位规则

要实现这个需求，核心是利用位并行运算避免逐位遍历，最大化CPU执行效率。以下是最优实现方案：

实现思路 #

1. 对每个ulong，快速检测其16个4位组中是否存在1，生成一个16位的标记值（每个位对应一个4位组的检测结果）。
2. 将每个ulong的16位标记值，放到最终掩码myMask的对应位置（第i个ulong的标记值左移i*16位）。
3. 通过位运算的并行处理，替代循环检测每个4位组，大幅提升效率。

代码实现（C#） #

private const ulong FourBitGroupMask = 0x0F0F0F0F0F0F0F0FUL;
private const ulong SingleBitExtractor = 0x0101010101010101UL;
private const ulong BitCompressor = 0x0001000100010001UL;

ulong GenerateGroupMask(List<ulong> qwords)
{
    ulong myMask = 0;
    for (int idx = 0; idx < qwords.Count; idx++)
    {
        ulong qword = qwords[idx];
        
        // 1. 提取所有4位组的原始位
        ulong groupBits = qword & FourBitGroupMask;
        // 2. 将组内任意1传播到组的最低位
        groupBits |= groupBits >> 1;
        groupBits |= groupBits >> 2;
        // 3. 仅保留每个组的最低位（1表示组内有1，0表示无）
        groupBits &= SingleBitExtractor;
        // 4. 把分散的16个位压缩到低16位（利用乘法的位对齐特性）
        ushort groupFlags = (ushort)((groupBits * BitCompressor) >> 48);
        // 5. 将标记值放到myMask的对应位置
        myMask |= (ulong)groupFlags << (idx * 16);
    }
    return myMask;
}

关键技巧说明 #

• 4位组检测：通过FourBitGroupMask提取每个4位组的所有位，再通过两次移位或运算，把组内任意1传播到组的最低位，这样只要组内有1，最低位就会变成1。
• 位压缩：BitCompressor是一个特殊的常量，和groupBits相乘后，会把每个4位组的标记位对齐到64位的高16位，右移48位就能直接得到16位的标记值，比循环移位效率高得多。
• 时间复杂度：O(N)（N为列表元素数量），每个元素的处理都是固定的常数时间位运算，无额外循环开销。

示例验证 #

对于输入List<ulong>() {0x1, 0x1, 0x1}：

• 每个ulong的处理结果都是0x1（仅第0个4位组有1）。
• 分别左移0位、16位、32位后进行或运算，得到0x1 | 0x10000 | 0x100000000 = 0x100010001，与示例结果完全一致。

内容的提问来源于stack exchange，提问作者Darek