c++ - 多类作业

Question

如何在位掩码上实现无循环操作，对于宽度为 n 的两个位掩码 a 和 b 给出位掩码 c 宽度 2 * n 具有以下属性:

• i - c 中的第 bit 仅当 a 中有 j -th bit 且k - b 和 j + k == i
中的第一个位

C++ 实现:

#include <bitset>
#include <algorithm>
#include <iostream>

#include <cstdint>
#include <cassert>

#include <x86intrin.h>

std::uint64_t multishift(std::uint32_t a, std::uint32_t b)
{
    std::uint64_t c = 0;
    if (_popcnt32(b) < _popcnt32(a)) {
        std::swap(a, b);
    }
    assert(a != 0);
    do {
        c |= std::uint64_t{b} << (_bit_scan_forward(a) + 1);
    } while ((a &= (a - 1)) != 0); // clear least set bit
    return c;
}

int main()
{
    std::cout << std::bitset< 64 >(multishift(0b1001, 0b0101)) << std::endl; // ...0001011010
}

是否可以使用一些位技巧或一些 x86 指令在没有循环的情况下重新实现它？

Answer 1

这就像使用 OR 而不是 ADD 的乘法。据我所知，没有真正惊人的技巧。但这里有一个实际上避免内部函数而不是使用它们的技巧:

while (a) {
    c |= b * (a & -a);
    a &= a - 1;
}

这与您的算法非常相似，但使用乘法将 b 左移 a 的尾随零计数，a & -a 是仅选择最低设置位作为掩码的技巧。作为奖励，该表达式在 a == 0 时可以安全执行，因此您可以展开(和/或将 while 转换为 do/while 没有前提条件)而不会出现令人讨厌的边缘情况(这是TZCNT 和 shift 不是这种情况。

---

pshufb 可用于并行查表模式，使用 a 的半字节选择一个子表，然后使用它乘以 的所有半字节>b 由一条指令中的 a 半字节组成。对于正确的乘法，最大为 8 个 pshufb(或始终为 8，因为尝试提前退出的意义不大)。它确实需要在开始时进行一些奇怪的设置和一些不幸的水平东西才能完成它，所以它可能不是那么好。