How to interleave 2 booleans using bitwise operators?

Question

Suppose I have two 4-bit values, ABCD and abcd. How to interleave it, so it becomes AaBbCcDd, using bitwise operators? Example in pseudo-C:

nibble a = 0b1001;
nibble b = 0b1100;
char c = foo(a,b);
print_bits(c); 
// output: 0b11010010

Note: 4 bits is just for illustration, I want to do this with two 32bit ints.

Answer 1

This is called the perfect shuffle operation, and it's discussed at length in the Bible Of Bit Bashing, Hacker's Delight by Henry Warren, section 7-2 "Shuffling Bits."

Assuming x is a 32-bit integer with a in its high-order 16 bits and b in its low-order 16 bits:

   unsigned int x = (a << 16) | b;   /* put a and b in place */

the following straightforward C-like code accomplishes the perfect shuffle:

x = (x & 0x0000FF00) << 8 | (x >> 8) & 0x0000FF00 | x & 0xFF0000FF;
x = (x & 0x00F000F0) << 4 | (x >> 4) & 0x00F000F0 | x & 0xF00FF00F;
x = (x & 0x0C0C0C0C) << 2 | (x >> 2) & 0x0C0C0C0C | x & 0xC3C3C3C3;
x = (x & 0x22222222) << 1 | (x >> 1) & 0x22222222 | x & 0x99999999;

He also gives an alternative form which is faster on some CPUs, and (I think) a little more clear and extensible:

unsigned int t;  /* an intermediate, temporary variable */
t = (x ^ (x >> 8)) & 0x0000FF00;  x = x ^ t ^ (t << 8);
t = (x ^ (x >> 4)) & 0x00F000F0;  x = x ^ t ^ (t << 4);
t = (x ^ (x >> 2)) & 0x0C0C0C0C;  x = x ^ t ^ (t << 2);
t = (x ^ (x >> 1)) & 0x22222222;  x = x ^ t ^ (t << 1);

I see you have edited your question to ask for a 64-bit result from two 32-bit inputs. I'd have to think about how to extend Warren's technique. I think it wouldn't be too hard, but I'd have to give it some thought. If someone else wanted to start here and give a 64-bit version, I'd be happy to upvote them.

EDITED FOR 64 BITS

I extended the second solution to 64 bits in a straightforward way. First I doubled the length of each of the constants. Then I added a line at the beginning to swap adjacent double-bytes and intermix them. In the following 4 lines, which are pretty much the same as the 32-bit version, the first line swaps adjacent bytes and intermixes, the second line drops down to nibbles, the third line to double-bits, and the last line to single bits.

unsigned long long int t;  /* an intermediate, temporary variable */
t = (x ^ (x >> 16)) & 0x00000000FFFF0000ull;  x = x ^ t ^ (t << 16);
t = (x ^ (x >> 8))  & 0x0000FF000000FF00ull;  x = x ^ t ^ (t << 8);
t = (x ^ (x >> 4))  & 0x00F000F000F000F0ull;  x = x ^ t ^ (t << 4);
t = (x ^ (x >> 2))  & 0x0C0C0C0C0C0C0C0Cull;  x = x ^ t ^ (t << 2);
t = (x ^ (x >> 1))  & 0x2222222222222222ull;  x = x ^ t ^ (t << 1);

Answer 2

From Stanford "Bit Twiddling Hacks" page: https://graphics.stanford.edu/~seander/bithacks.html#InterleaveTableObvious

 uint32_t x = /*...*/, y = /*...*/;
 uint64_t z = 0;

 for (int i = 0; i < sizeof(x) * CHAR_BIT; i++) // unroll for more speed...
 {
     z |= (x & 1U << i) << i | (y & 1U << i) << (i + 1);
 }

Look at the page they propose different and faster algorithms to achieve the same.