合并两个具有冲突解决的位掩码，任意两个设置位之间有一些所需的距离

Question

我有两个整数值： d_a = 6和d_b = 3，所谓位距。使用适当距离创建的蒙版如下所示：

uint64_t a = 0x1041041041041041; // 0001 0000 0100 0001 0000 0100 0001 0000
                                // 0100 0001 0000 0100 0001 0000 0100 0001

uint64_t b = 0x9249249249249249; // 1001 0010 0100 1001 0010 0100 1001 0010
                                 // 0100 1001 0010 0100 1001 0010 0100 1001

目标是有一个 target 掩码，它的位设置为 d_b，但同时考虑到 a 掩码中设置的位（例如，第一个设置位是转移）。

第二件事是 target 掩码中的距离不是恒定的，即 target 掩码中设置位之间的零数应等于 d_b 或增加它们之间的位设置为 a

uint64_t target = 0x4488912224488912; // 0100 0100 1000 1000 1001 0001 0010 0010
                                      // 0010 0100 0100 1000 1000 1001 0001 0010

形象化问题的图片：

蓝色条是 a，黄色是 b。我宁愿使用位操作内在函数而不是逐位操作。

编辑：实际上，我有以下代码，但我正在寻找指令数量较少的解决方案。

void set_target_mask(int32_t d_a, int32_t d_b, int32_t n_bits_to_set, uint8_t* target)
{
    constexpr int32_t n_bit_byte = std::numeric_limits<uint8_t>::digits;

    int32_t null_cnt = -1;

    int32_t n_set_bit = 0;
    int32_t pos = 0;
    while(n_set_bit != n_bits_to_set)
    {
        int32_t byte_idx = pos / n_bit_byte;
        int32_t bit_idx = pos % n_bit_byte;

        if(pos % d_a == 0)
        {
            pos++;
            continue;
        }
        null_cnt++;

        if(null_cnt % d_b == 0)
        {
            target[byte_idx] |= 1 << bit_idx;
            n_set_bit++;
        }
        pos++;
    }
}

Answer 1

如果目标是 uint64_t，可能 d_a 和 d_b 可以通过查找 table 转换为位掩码。喜欢你的问题 lut[6] == 0x2604D5C99A01041。

查找 tables 可以在每个程序运行初始化期间初始化一次，或者在编译时使用宏或常量表达式 (constexpr)。

要使 d_b 展开，跳过 d_a 位，您可以使用 pdep 和反转 d_a:

 uint64_t tmp = _pdep_u64(d_b_bits, ~d_a_bits);

然后你可以将n_bits_to_set转换为连续位掩码：

 uint64_t n_bits = (1 << n_bits_to_set) - 1;

并再次使用 pdep 传播它们：

 uint64_t tmp = _pdep_u64(n_bits, tmp);

（请参阅 Intrinsic Guide 关于 pdep。请注意，pdep 在 Zen3 之前的 AMD 上速度较慢。它在 Intel CPU 和 Zen3 上速度很快，但在 Bulldozer 系列或 Zen1/Zen2 上则不然）

合并两个具有冲突解决的位掩码，任意两个设置位之间有一些所需的距离

Merge two bitmask with conflict resolving, with some required distance between any two set bits

c++

x86

bit-manipulation

intrinsics