如何有效地解交织比特(逆莫顿)

Question

这个问题:如何解交织比特(UnMortonizing？)有一个很好的答案,可以提取莫顿数的两半中的一个(只是奇数位),但我需要一个解决方案来提取两个部分(奇数位和尽可能少的操作.

对于我的使用,我需要采用32位int并提取两个16位整数,其中一个是偶数位,另一个是奇数位右移1位,例如

input,  z: 11101101 01010111 11011011 01101110

output, x: 11100001 10110111 // odd bits shifted right by 1
        y: 10111111 11011010 // even bits

似乎有很多解决方案使用带有幻数的移位和掩码来生成Morton数(即交错位),例如Binary Magic Numbers的Interleave位,但我还没有发现任何反向(即去交错) .

UPDATE

在重新阅读Hacker's Delight中关于完美洗牌/洗牌的部分后,我找到了一些有用的例子,我改编如下:

// morton1 - extract even bits

uint32_t morton1(uint32_t x)
{
    x = x & 0x55555555;
    x = (x | (x >> 1)) & 0x33333333;
    x = (x | (x >> 2)) & 0x0F0F0F0F;
    x = (x | (x >> 4)) & 0x00FF00FF;
    x = (x | (x >> 8)) & 0x0000FFFF;
    return x;
}

// morton2 - extract odd and even bits

void morton2(uint32_t *x, uint32_t *y, uint32_t z)
{
    *x = morton1(z);
    *y = morton1(z >> 1);
}

我认为这仍然可以改进,无论是当前的标量形式还是利用SIMD,所以我仍然对更好的解决方案(标量或SIMD)感兴趣.

Answer 1

如果您的处理器有效处理64位整数,您可以组合操作...

int64 w = (z &0xAAAAAAAA)<<31 | (z &0x55555555 )
w = (w | (w >> 1)) & 0x3333333333333333;
w = (w | (w >> 2)) & 0x0F0F0F0F0F0F0F0F; 
...

Answer 2

Intel Haswell及更高版本CPU的代码.您可以使用包含pext和pdep指令的BMI2指令集.这些可以(以及其他伟大的事情)用于构建您的功能.

#include <immintrin.h>
#include <stdint.h>

// on GCC, compile with option -mbmi2, requires Haswell or better.

uint64_t xy_to_morton (uint32_t x, uint32_t y)
{
    return _pdep_u32(x, 0x55555555) | _pdep_u32(y,0xaaaaaaaa);
}

uint64_t morton_to_xy (uint64_t m, uint32_t *x, uint32_t *y)
{
    *x = _pext_u64(m, 0x5555555555555555);
    *y = _pext_u64(m, 0xaaaaaaaaaaaaaaaa);
}

Answer 3

如果有人在 3d 中使用 morton 代码，那么他需要每 3 位读取一位，这里的 64 位是我使用的函数：

uint64_t morton3(uint64_t x) {
    x = x & 0x9249249249249249;
    x = (x | (x >> 2))  & 0x30c30c30c30c30c3;
    x = (x | (x >> 4))  & 0xf00f00f00f00f00f;
    x = (x | (x >> 8))  & 0x00ff0000ff0000ff;
    x = (x | (x >> 16)) & 0xffff00000000ffff;
    x = (x | (x >> 32)) & 0x00000000ffffffff;
    return x;
}
uint64_t bits; 
uint64_t x = morton3(bits)
uint64_t y = morton3(bits>>1)
uint64_t z = morton3(bits>>2)