Serge Rogatch - 5 months ago 29

C++ Question

I need to make

`uint64_t`

`uint32_t`

`A=a0a1a2...a31`

`B=b0b1...b31`

`a0b0a1b1...a31b31`

`for`

`C|=((A&(1<<i))<<i)|((B&(1<<i))<<(i+1))`

I guess there should be some mathematical trick like multiplying A and B by some special number which results in interleaving their bits with zeros in the resulting 64-bit number, so that what only remains is to

`or`

Another potential way to go is a compiler intrinsic or assembly instruction, but I don't know of such.

Answer

NathanOliver's link offers the 16-bit -> 32-bit implementation:

```
static const unsigned int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF};
static const unsigned int S[] = {1, 2, 4, 8};
unsigned int x; // Interleave lower 16 bits of x and y, so the bits of x
unsigned int y; // are in the even positions and bits from y in the odd;
unsigned int z; // z gets the resulting 32-bit Morton Number.
// x and y must initially be less than 65536.
x = (x | (x << S[3])) & B[3];
x = (x | (x << S[2])) & B[2];
x = (x | (x << S[1])) & B[1];
x = (x | (x << S[0])) & B[0];
y = [the same thing on y]
z = x | (y << 1);
```

Which works by:

- leave the low 8 bits of x where they are. Move the high 8 bits up by 8;
- divide in half and do the same thing, this time leaving the low pairs of 4 bits where they are and moving the others up by 4;
- and again, and again.

I.e. it proceeds as:

```
abcdefghijklmnop
-> 00000000abcdefgh 00000000ijklmnop
-> 0000abcd0000efgh 0000ijkl0000mnop
-> 00ab00cd00ef00gh 00ij00kl00mn00op
-> 0a0b0c0d0e0f0g0h 0i0j0k0l0m0n0o0p
```

And then combines the two inputs together.

As per my earlier comment, to extend that to 64 bits, just add an initial shift by 16 and mask by `0x0000ffff0000ffff`

, either because you can intuitively follow the pattern or as a divide-and-conquer step, turning the 32-bit problem into two non-overlapping 16-bit problems and then using the 16-bit solution.