Here is a portable C++ implementation. It seems to work during my brief testing. The deinterleave code is based on this SO question.
uint64_t calc(uint64_t n)
{
// (odd | even)
uint64_t x = (n & 0x5555555555555555ull) | ((n & 0xAAAAAAAAAAAAAAAAull) >> 1);
// deinterleave
x = (x | (x >> 1)) & 0x3333333333333333ull;
x = (x | (x >> 2)) & 0x0F0F0F0F0F0F0F0Full;
x = (x | (x >> 4)) & 0x00FF00FF00FF00FFull;
x = (x | (x >> 8)) & 0x0000FFFF0000FFFFull;
x = (x | (x >> 16)) & 0x00000000FFFFFFFFull;
return x;
}
gcc, clang, and msvc all compile this down to about 30 instructions.
From the comments, there is a modification that can be made.
- Change the first line to use a single bitmask operation to select only the “odd” bits.
The possibly (?) improved code is:
uint64_t calc(uint64_t n)
{
// (odd | even)
uint64_t x = (n | (n >> 1)) & 0x5555555555555555ull; // single bits
// ... the restdeinterleave
x = (x | (x >> 1)) & 0x3333333333333333ull; // bit pairs
x = (x | (x >> 2)) & 0x0F0F0F0F0F0F0F0Full; // nibbles
x = (x | (x >> 4)) & 0x00FF00FF00FF00FFull; // octets
x = (x | (x >> 8)) & 0x0000FFFF0000FFFFull; // halfwords
x = (x | (x >> 16)) & 0x00000000FFFFFFFFull; // words
return x;
}