如何去交织比特（UnMortonizing？） [英] How to de-interleave bits (UnMortonizing?)

问题描述

什么是去交错位从32位的int的最有效方法是什么？对于这种特殊的情况下，我只关心奇怪的位，但我敢肯定它的简单概括的任何解决方案，这两套。

What is the most efficient way to de-interleave bits from a 32 bit int? For this particular case, I'm only concerned about the odd bits, although I'm sure it's simple to generalize any solution to both sets.

例如，我想 0b01000101 转换成 0b1011 。什么是最快的方法？

For example, I want to convert 0b01000101 into 0b1011. What's the quickest way?

编辑：

在本申请中，我可以保证，即使位全部为零。我可以把这个事实的优势，以提高速度或减少空间？

In this application, I can guarantee that the even bits are all zeros. Can I take advantage of that fact to improve speed or reduce space?

推荐答案

既然你知道，所有其他位应用程序为0，你可以做这样的：

Given that you know that every other bit is 0 in your application, you can do it like this:

x = (x | (x >> 1)) & 0x33333333;
x = (x | (x >> 2)) & 0x0f0f0f0f;
x = (x | (x >> 4)) & 0x00ff00ff;
x = (x | (x >> 8)) & 0x0000ffff;

第一步看起来是这样的：

The first step looks like this:

  0a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p   x
| 00a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0   x >> 1
  --------------------------------
= 0aabbccddeeffgghhiijjkkllmmnnoop   x | (x >> 1)
& 00110011001100110011001100110011   0x33333333
  --------------------------------
= 00ab00cd00ef00gh00ij00kl00mn00op   (x | (x >> 1)) & 0x33333333

然后，第二步骤的两个位工作的时间，等等。

Then the second step works with two bits at a time, and so on.

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