使用掩码交错位

Question

输入：

arbitrary bitset, e.g. bit positions 012345
arbitrary bit mask, e.g. (x=1) xx0x0x

输出：

xx0x1x2345

也就是说，我希望将位集的第一位放置在掩码的第一个 0 中。同样，第二位被放置在掩码的第二个 0 中。

示例：

mask = 1001001
bits = 1101
result = 1111011

我知道这可以通过循环来完成，但我想主要使用位操作来完成。我知道您可以仅使用掩码和位运算符来执行任意位排列。我愿意花费大量时间来设置排列掩码，因为输入掩码将被多次使用。

编辑：我查看了 http://graphics.stanford.edu/~ 的算法seander/bithacks.html 和 http://www.hackersdelight.org/HDcode.htm< /a>，但还没有找到确切的方法。

Answer 1

我认为 012345 旨在成为一个 BITSET，他使用 0..5 来指示 0 和 1 的混合。

然而，这似乎不是按位运算。我会坚持循环..

Answer 2

如果我没有理解错的话，你需要一个函数 f(bitmask, bitset) ，例如：

f(0b00110101, 0b000ABCDE) = 0bABC11D1E1

其中第一个参数（位掩码）相对固定。

我认为您必须循环位掩码，并且在该循环内您可以使用按位运算。当然，您可以预先编译位掩码并保留 0 的位置，如 {1, 3, 6, 7, ...}，并通过循环序列来节省一些周期。

Answer 3

你确定你不需要循环吗？如果您知道位数，则可以跳过开销，只需执行 16 或 32 行位移即可，但循环会更简单。我认为确实没有其他方法可以做到这一点，但你现在让我开始思考它

Answer 4

我认为您想要实现的效果是（使用您的示例数据，但以不同的方式布置信息）：

bitmask = 1001001
bitset  =  11 01
result  = 1111011

现在，如果我们将其描述为从右到左工作（首先是最低有效位），那么最后的 1 bitset 表示需要设置位掩码最右边的 0。位集中的 0 表示位掩码的下一个 0 不变；接下来的1表示将第三个0转换为1；最重要的 1 意味着第四个零转换为 1。由于位集中没有更多的 1，因此这是最终的更改。请注意，这种算法的表述避免了位集或位掩码中有多少位的问题 - 而从左到右的解释会导致大问题。

让我们回顾一些其他示例：

bitmask = 1001001      1001001      1100011000   0000000101001001
bitset  =  11 00        10 00         110  010     11100 1 00 11
result  = 1111001      1101001      1111011010   0011100111001111


bitmask = 01001101     01001011     11000010     0000000011111111
bitset  = 1 10  1      1 10 1          110 1         1101
result  = 11101111     11101111     11011011     0000110111111111

如果此解释正确，则位集的含义会根据位掩码而变化。如果位掩码和位集限制为 8 位，那么对于每个位集，您可能最终会计算一组 256 个值，这些值可以与原始位掩码值进行或运算以产生结果。另一方面，您可以轻松地将结果计算为与主数据进行“或”运算的值。

Answer 5

大多数交错位或通用聚合位函数都会循环，但以不明显的方式循环。

即使是计数位函数也具有 O(log2(整数位)) 复杂度。

因此，如果您愿意接受 O(掩码中的零数) 循环，那么这可能是您最好的选择。 （您必须有一个算法，无论如何都可以在没有本机 插入位的情况下执行此操作说明。）：

unsigned blah(unsigned bitmask, unsigned bits_to_insert)
{
    unsigned insertion_bitmask= ~bitmask;

    while (insertion_bitmask)
    {
        unsigned bit_position_to_insert= insertion_bitmask & -insertion_bitmask;
        unsigned current_bit= bits_to_insert & 1;
        unsigned bit_to_insert_into_mask= (-current_bit) & bit_position_to_insert;
        bitmask|= bit_to_insert_into_mask;

        bits_to_insert>>= 1;
        insertion_bitmask&= insertion_bitmask - 1;
    }

    return bitmask;
}