如何有效地去交织比特（逆莫顿）

问题描述

此问题：对提取莫顿数（只是奇数位）的两半的一个很好的答案，但我需要它提取在尽可能少的操作两部分（奇数位和偶数位）的解决方案。

有关我的使用，我需要采取一个32位整型和提取两个16位整数，其中一个是偶数位，另一种是奇数位1位，例如

右移

 输入，Z：11101101 01010111 11011011 01101110输出，X：11100001 10110111 //奇数位1右移
        Y：10111111 11011010 //偶数位
 

似乎有充足的使用变化和口罩幻数生成莫顿数字（即交错位）的解决方案，例如由二进制幻数 交错位，但我还没有找到任何东西做反向（即解交织）。

更新

在重新阅读从黑客对完美的洗牌/ unshuffles喜悦，我发现，我适应了一些有用的例子节之后如下：

  // morton1  - 提取偶数位uint32_t的morton1（uint32_t的X）
{
    X = X＆放大器; 0x55555555;
    X =（X |（X GT;→1））及0x33333333;
    X =（X |（X GT;＆→2））及0x0F0F0F0F;
    X =（X |（X GT;＆→4））及0x00FF00FF;
    X =（X |（X GT;→8））及0x0000FFFF;
    返回X;
}// morton2  - 提取奇数和偶数位无效morton2（uint32_t的* X，uint32_t的* Y，uint32_t的Z）
{
    * X = morton1（z）的;
    * Y = morton1（Z＆GT;大于1）;
}
 

我觉得这还是可以改进，无论是在目前的标量的形式，也采取SIMD的优势，所以我仍然有兴趣更好的解决方案（无论是标量或SIMD）。

解决方案

如果您的处理器处理64位整数有效，你可以结合的操作...

 的Int64 W =（Z＆安培; 0xAAAAAAAA）LT;＆LT; 31 | （Z＆安培; 0x55555555）
W =（W |（并且R w→1））及0x3333333333333333;
W =（W |（并且R w→2））及0x0F0F0F0F0F0F0F0F;
...
 

This question: How to de-interleave bits (UnMortonizing?) has a good answer for extracting one of the two halves of a Morton number (just the odd bits), but I need a solution which extracts both parts (the odd bits and the even bits) in as few operations as possible.

For my use I would need to take a 32 bit int and extract two 16 bit ints, where one is the even bits and the other is the odd bits shifted right by 1 bit, e.g.

input,  z: 11101101 01010111 11011011 01101110

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

There seem to be plenty of solutions using shifts and masks with magic numbers for generating Morton numbers (i.e. interleaving bits), e.g. Interleave bits by Binary Magic Numbers, but I haven't yet found anything for doing the reverse (i.e. de-interleaving).

UPDATE

After re-reading the section from Hacker's Delight on perfect shuffles/unshuffles I found some useful examples which I adapted as follows:

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

I think this can still be improved on, both in its current scalar form and also by taking advantage of SIMD, so I'm still interested in better solutions (either scalar or SIMD).

解决方案

If your processor handles 64 bit ints efficiently, you could combine the operations...

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

这篇关于如何有效地去交织比特（逆莫顿）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！