bit-manipulation - 位操作如何有效地交叉交织位( 逆 Morton )

  显示原文与译文双语对照的内容

This的问题是如何在 Morton number中提取两个部分的一个,但是我需要一个解,以尽可能少的运算提取两个部分。

在使用时,需要取一个32位int并提取两个 ints int,其中一个是偶数位,另一个是奇数位,e.g. 位 shifted


input, z: 11101101 01010111 11011011 01101110



output, x: 11100001 10110111//odd bits shifted right by 1


 y: 10111111 11011010//even bits



似乎有很多解决方案使用移动和掩码的魔术数字生成for数字( 例如 ) 。 交错位),比如 交织位由二进制幻数,但是我还没有找到做反向运算的任何事情( 例如 ) 。 de交错) 。

更新

在阅读了完美洗牌/unshuffles的黑客部分之后,我发现一些有用的例子,我如下所做:


//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);


}



我认为这仍然可以改进,既可以在当前标量形式,也可以利用 vxml,我仍然感兴趣的解决方案( 标量或者 SIMD ) 。

时间: 原作者:

如果处理器高效处理 64位 int,则可以组合操作。


int64 w = (z &0xAAAAAAAA)<<31 | (z &0x55555555 )


w = (w | (w>> 1)) & 0x3333333333333333;


w = (w | (w>> 2)) & 0x0F0F0F0F0F0F0F0F; 


...



原作者:

英特尔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);


}



如果有人在 3使用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)



如果需要速度比你可以使用表查找一次对一个字节转换,( 两个字节表更快,但要大) 。 程序是在 Delphi IDE下进行的,但汇编/剪裁是相同的。


const


 MortonTableLookup : array[byte] of byte = ($00, $01, $10, $11, $12,.. . ;



procedure DeinterleaveBits(Input: cardinal);


//In: eax


//Out: dx = EvenBits; ax = OddBits;


asm


 movzx ecx, al//Use 0th byte


 mov dl, byte ptr[MortonTableLookup + ecx]


//


 shr eax, 8


 movzx ecx, ah//Use 2th byte


 mov dh, byte ptr[MortonTableLookup + ecx]


//


 shl edx, 16


 movzx ecx, al//Use 1th byte


 mov dl, byte ptr[MortonTableLookup + ecx]


//


 shr eax, 8


 movzx ecx, ah//Use 3th byte


 mov dh, byte ptr[MortonTableLookup + ecx]


//


 mov ecx, edx 


 and ecx, $F0F0F0F0


 mov eax, ecx


 rol eax, 12


 or eax, ecx



 rol edx, 4


 and edx, $F0F0F0F0


 mov ecx, edx


 rol ecx, 12


 or edx, ecx


end;



原作者:
...