Concatenating two bit patterns

Question

I need to merge two variables. They both are unsigned ints.

• First: 11000000
• Second: 11111010000

Desired output: 11011111010000

In words: I need to put all the 1 followed by one 0 (in first number) in front of the whole second number. The only think that come to my mind is, to bit shift the first number to the left as many as the length of the second is. And than sum it. But i don't know the length. Though it probably could be found, isn't there a better easier way?

Thx

Answer 1

Here's a solution which runs in constant time:

You can compute the position of the first 1-bit of x by (int)(log(x)/log(2)).

Furthermore, you can compute the number of trailing zeros of x by a neat trick shown here: http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightMultLookup

Hence, your program might look something like this:

int x, y;
int lookuptable[32] = { 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25,
                        17, 4, 8, 31, 27, 13, 23, 21, 19, 16, 7, 26, 
                        12, 18, 6, 11, 5, 10, 9 };

int tail_x = lookuptable[(((x & -x) * 0x077CB531U)) >> 27];
int size_y = (int)(log(y) / log(2)) + 1;

if (tail_x - size_y <= 0) {
        x <<= size_y - tail_x + 1;
} else {
        x >>= tail_x - size_y - 1;
}       

x |= y;

Now, x contains the result of appending y to x as specified by the OP. Note that you need slight adjustments for non 32-bit machines.