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.htmlhttp://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 回答