什么是在软件中模拟 PDEP 和 PEXT 的快速回退算法？

Question

我想围绕 x86 指令PDEP（并行位存储）和PEXT（并行位提取）创建一个包装器。在这些不可用的架构上（并且相应的内在函数也不可用），我需要一个快速的回退实现。

32 位整数的朴素算法如下所示：

constexpr std::uint32_t bit_deposit(std::uint32_t src, std::uint32_t mask) {
    std::uint32_t result = 0;
    for (std::uint32_t src_pos = 0, mask_pos = 0; mask_pos != 32; ++mask_pos) {
        if (mask >> mask_pos & 1) {
            result |= (src >> src_pos++ & 1) << mask_pos;
        }
    }
    return result;
}

static_assert(bit_deposit(0b000, 0b000000) == 0b000000);
static_assert(bit_deposit(0b101, 0b101010) == 0b100010);
static_assert(bit_deposit(0b111, 0b101010) == 0b101010);

constexpr std::uint32_t bit_extract(std::uint32_t src, std::uint32_t mask) {
    std::uint32_t result = 0;
    for (std::uint32_t src_pos = 0, mask_pos = 0; mask_pos != 32; ++mask_pos) {
        if (mask >> mask_pos & 1) {
            result |= (src >> mask_pos & 1) << src_pos++;
        }
    }
    return result;
}

static_assert(bit_extract(0b000000, 0b000000) == 0b000);
static_assert(bit_extract(0b100010, 0b101010) == 0b101);
static_assert(bit_extract(0b101010, 0b101010) == 0b111);

有没有一种方法可以显着改善这一点？当前的算法是 O(n)，我怀疑存在 O(log n) 解决方案。

对于许多其他位操作操作，有对数算法（从单位移位到多位移位、填充计数、舍入到下一个 2 的幂等）。因此，我怀疑比特存款和比特提取也存在类似的情况。

Answer 1

在 Hacker's Delight 第 7 章中，重新排列位和字节，有这样的扩展实现：

unsigned expand(unsigned x, unsigned m) {
    unsigned m0, mk, mp, mv, t;
    unsigned array[5];
    int i;
    m0 = m; // Save original mask.
    mk = ~m << 1; // We will count 0's to right.
    for (i = 0; i < 5; i++) {
        mp = mk ^ (mk << 1); // Parallel suffix.
        mp = mp ^ (mp << 2);
        mp = mp ^ (mp << 4);
        mp = mp ^ (mp << 8);
        mp = mp ^ (mp << 16);
        mv = mp & m; // Bits to move.
        array[i] = mv;
        m = (m ^ mv) | (mv >> (1 << i)); // Compress m.
        mk = mk & ~mp;
    }
    for (i = 4; i >= 0; i--) {
        mv = array[i];
        t = x << (1 << i);
        x = (x & ~mv) | (t & mv);
    }
    return x & m0; // Clear out extraneous bits.
}

这个压缩的实现：

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 suffix.
        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;
}

这些不会k对k-bit 整数进行迭代，但我不知道这实际上是否是一个好方法。我听说有传言说你可以做得更好，但我还没听说过如何做，也许这根本不是真的。