interleaving bits with a mask

Question

inputs:

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

output:

xx0x1x2345

That is, I want the first bit of the bitset to be placed in the first 0 of the mask. Likewise, the second bit is placed in the second 0 of the mask.

example:

mask = 1001001
bits = 1101
result = 1111011

I know that this can be done with a loop, but I'd like do it using primarily bit operations. I know you can perform arbitrary bit permutations using only masking and bit operators. I'm willing to spend a good amount of time setting up the permutation masks since the input mask will be used many times.

edit: I've looked at the algorithms at http://graphics.stanford.edu/~seander/bithacks.html and http://www.hackersdelight.org/HDcode.htm, but haven't found the exact method yet.

Answer 1

I think the 012345 is intended to be a BITSET and he used 0..5 to indiccate a mix of 0's and 1s.

However, this does not appear to be a bitwise operation. I'd stick to a loop..

Answer 2

are you sure you don't need a loop? If you know the number of bits you could skip the overhead and just do like 16 or 32 lines of bit shifts, but a loop would be simpler. I don't think there's really another way to do it but you got me thinking about it now

Answer 3

If I didn't get it wrong, you want a function f(bitmask, bitset) like:

f(0b00110101, 0b000ABCDE) = 0bABC11D1E1

in which the first argument (the bit mask) is relatively fixed.

I think you'll have to loop over the bit mask, and inside that loop you could use bitwise operation. Of course you can compile the bit mask beforehand and keep the positions of 0's like {1, 3, 6, 7, ...}, and save some cycles by looping over the sequence instead.

Answer 4

I think that the effect you are trying to achieve is (using your example data, but laying the information out somewhat differently):

bitmask = 1001001
bitset  =  11 01
result  = 1111011

Now, if we describe this as working from right to left (least significant bit first), then the final 1 of the bitset means that the rightmost 0 of the bitmask needs to be set. The zero in the bitset means that the next 0 of the bitmask is unchanged; the next 1 means that the third zero is converted to a one; and the most significant 1 means that the fourth zero is converted to a 1. Since there are no more ones in the bitset, that is the final change. Note that this formulation of the algorithm avoid issues with how many bits there are in the bitset or bitmask - whereas a left to right interpretation leads to big problems.

Let's review some other examples:

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

If this interpretation is correct, then the meaning of the bitset varies depending on the bitmask. If the bitmask and bitset are limited to 8 bits, then for each bitset, you probably end up computing a set of 256 values that can be OR'd with the original bitmask value to produce the result. On the other hand, you can just as easily compute the result as a value to be OR'd into the main data.

Answer 5

Most of the interleave bits or general aggregate bits functions do loop, but in a non-obvious way.

Even the count bits function has an O(log2(bits in integer)) complexity.

So if you are willing to accept an O(# of zeroes in mask) loop, then that will probably be your best bet. (You'd have to have an algorithm that does that anyway without a native insert bits instruction.):

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;
}