Join bits using bitwise operations. Is this even possible?

Question

What I am asking is if it is possible to join all bits in 2 different numbers.

A pseudo-code example:

bytes=array(0x04, 0x3F);

//place bitwise black magic here

print 0x043F;

Another example:

bytes=array(0xFF, 0xFFFF);

//place bitwise black magic here

print 0xFFFFFF;

Yet another example:

bytes=array(0x34F3, 0x54FD);

//place bitwise black magic here

print 0x34F354FD;

I want to restrict this to only and only bitwise operators (>>, <<, |, ^, ~ and &).

This should work at least in PHP and Javascript.

Is this possible in ANY way?

If I'm not being clear, please ask your doubts in a comment.

Answer 1

If I understand your question correctly,
This should be the answer in php:

    $temp = $your_first_value << strlen(dechex($the_length_of_the_second_value_in_hex))
    $result = $temp | $your_second_value
    print dechex($result)

Update: instead of + use the | operator

Answer 2

Depending on what endian-ness your machine is, you might have to reverse the order of bytes[0] and bytes1 below:

uint8_t  bytes[2] = { 0x04, 0x3f };
uint16_t result = (bytes[0] << 8) | bytes[1];

(This is in C, shouldn't be hard to translate to PHP etc., the languages and operators are similar enough)

Update: OK, now that you've clarified what you want, the basic approach is still the same. What you can do instead is count the number of bits in the right number, then do the bitshift as above on the left number, just with the dynamic number of bits. This works as long as you don't have more bits than fit into the largest numeric type that your language/platform support, so in this example 64 bits.

int  rightMaxBits = 0;
uint64_t leftNum = 0x04, rightNum = 0x3f;
uint64_t rightNumCopy = rightNum;

while( rightNumCopy )
{
    rightNumCopy >>= 1;
    rightMaxBits++;
}

uint64_t resultNum = (leftNum << rightMaxBits) | rightNum;

(Thanks for the bit-counting algo to this SO thread) For signed numbers, I'd suggest you use abs() on the numbers before you call this and then later re-apply the sign in whatever way you want.

Answer 3

This problem hinges completely on being able to determine the position of the leftmost 1 in an integer. One way to do that is by "smearing the bits right" and then counting the 1's:

Smearing to the right:

int smearright(int x) {
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    return x;
}

Easy, only bitwise operators there. Counting the bits however involves some sort of addition:

int popcnt(int x) {
    x = add(x & 0x55555555, (x >> 1) & 0x55555555);
    x = add(x & 0x33333333, (x >> 2) & 0x33333333);
    x = add(x & 0x0f0f0f0f, (x >> 4) & 0x0f0f0f0f);
    x = add(x & 0x00ff00ff, (x >> 8) & 0x00ff00ff);
    x = add(x & 0xffff, (x >> 16) & 0xffff);
    return x;
}

But that's OK, add can be implemented as

int add(int x, int y) {
    int p = x ^ y;
    int g = x & y;
    g |= p & (g << 1);
    p &= p << 1;
    g |= p & (g << 2);
    p &= p << 2;
    g |= p & (g << 4);
    p &= p << 4;    
    g |= p & (g << 8);
    p &= p << 8;
    g |= p & (g << 16);
    return x ^ y ^ (g << 1);
}

Putting it together:

join = (left << popcnt(smearright(right))) | right;

It's obviously much easier if you had addition (no add function), perhaps surprisingly though, it's even simpler than that with multiplication:

join = (left * (smearright(right) + 1)) | right;

No more popcnt at all!

Implementing multiplication in terms of bitwise operators wouldn't help, that's much worse and I'm not sure you can even do it with the listed operators (unless the right shift is an arithmetic shift, but then it's still a terrible thing involving 32 additions each of which are function themselves).

There were no "sneaky tricks" in this answer, such as using conditions that implicitly test for equality with zero ("hidden" != 0 in an if, ?:, while etc), and the control flow is actually completely linear (function calls are just there to prevent repeated code, everything can be inlined).

---

Here's an alternative. Instead of taking the popcnt, do a weird variable shift:

int shift_by_mask(int x, int mask) {
    x <<= mask & 1;
    mask >>= 1;
    x <<= mask & 1;
    mask >>= 1;
    x <<= mask & 1;
    mask >>= 1;
    x <<= mask & 1;
    mask >>= 1;
    x <<= mask & 1;
    mask >>= 1;
    x <<= mask & 1;
    mask >>= 1;
    x <<= mask & 1;
    mask >>= 1;
    x <<= mask & 1;
    mask >>= 1;
    x <<= mask & 1;
    mask >>= 1;
    x <<= mask & 1;
    mask >>= 1;
    x <<= mask & 1;
    mask >>= 1;
    x <<= mask & 1;
    mask >>= 1;
    x <<= mask & 1;
    mask >>= 1;
    x <<= mask & 1;
    mask >>= 1;
    x <<= mask & 1;
    mask >>= 1;
    x <<= mask & 1;
    mask >>= 1;
    x <<= mask & 1;
    mask >>= 1;
    x <<= mask & 1;
    mask >>= 1;
    x <<= mask & 1;
    mask >>= 1;
    x <<= mask & 1;
    mask >>= 1;
    x <<= mask & 1;
    mask >>= 1;
    x <<= mask & 1;
    mask >>= 1;
    x <<= mask & 1;
    mask >>= 1;
    x <<= mask & 1;
    mask >>= 1;
    x <<= mask & 1;
    mask >>= 1;
    x <<= mask & 1;
    mask >>= 1;
    x <<= mask & 1;
    mask >>= 1;
    x <<= mask & 1;
    mask >>= 1;
    x <<= mask & 1;
    mask >>= 1;
    x <<= mask & 1;
    mask >>= 1;
    x <<= mask & 1;
    mask >>= 1;
    x <<= mask & 1;
    return x;
}

Ok that doesn't make me happy, but here's how you'd use it:

join = shift_by_mask(left, smearright(right)) | right;