2

输入：

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

输出：

xx0x1x2345

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

例子：

mask = 1001001
bits = 1101
result = 1111011

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

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

4

5 回答 5

1

如果我没有弄错，您需要一个函数 f(bitmask, bitset) ，例如：

f(0b00110101, 0b000ABCDE) = 0bABC11D1E1

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

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

于 2009-08-22T06:09:20.533 回答
1

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

但是，这似乎不是按位运算。我会坚持一个循环..

于 2009-08-22T05:38:15.823 回答
0

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

于 2009-08-22T06:02:43.620 回答
0

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

甚至 count bits 函数也具有 O(log2(bits in integer)) 复杂度。

因此，如果您愿意接受 O(# of zeroes in mask) 循环，那么这可能是您最好的选择。（你必须有一个算法，在没有本机插入位指令的情况下无论如何都可以做到这一点。）：

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;
}
于 2009-08-23T23:38:59.440 回答
0

我认为您要达到的效果是（使用您的示例数据，但信息的排列方式有所不同）：

bitmask = 1001001
bitset  =  11 01
result  = 1111011

现在，如果我们将其描述为从右到左工作（最低有效位在前），那么位集的最后一个 1 意味着需要设置位掩码的最右边的 0。bitset 中的 0 表示位掩码的下一个 0 不变；下一个 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 个值，这些值可以与原始位掩码值进行或运算以产生结果。另一方面，您可以轻松地将结果计算为要与主数据进行或运算的值。

于 2009-08-23T02:07:56.243 回答