byte - 交换字节中的每一对位

Question

这是 NVIDIA 代表在招聘会上提出的一个问题：

编写小而高效的代码来交换一个字节内的每一对位；例如，10 11 01 10应该变成01 11 10 01.

for有没有比通过所有其他索引循环更“有效”的方法来做到这一点？我的代码很小，但我想不出这可能比循环更“有效”......我猜可能有一种方法可以使用 XOR 来避免循环，但我不能想办法。

谢谢！

score 14 · Accepted Answer

像这样的东西应该工作

(i >> 1) & 01010101 + (i << 1) & 10101010

i >> 1将所有内容向右移动 1 位，& 01010101仅在偶数位置留下位。
第二部分以相同的方式处理奇数位位置。

不过，不确定它的效率如何。

score 12 · Accepted Answer

您可以使用包含 256 个条目的查找表。

或者，((x & 0x55) << 1) | ((x & 0xAA) >> 1)。

score 2 · Accepted Answer

如果没有查找表（或首先生成事物），您还可以：

10 11 01 10

左移是 01 10 11 00 用 10101010 屏蔽给我们 00 10 10 00

右移（原始）是 01 01 10 11 用 01010101 掩盖给我们 01 01 00 01

或者我们的结果一起

01 11 10 01

所以在 C 或 C++ 中你可以做

unsigned char bitswap( unsigned char uch )
{
   return ((uch<<1) & 0xAA) | (uch>>1) & 0x55 );
}

只需对从 0x00 到 0xff 的所有值运行它（确保您的循环终止！）以生成您的“表”。

score 1 · Accepted Answer

1

表查找（除非他正在寻找一些特定的 NVIDA 特定解决方案）。

于 2011-01-25T00:32:06.793 回答

score 1 · Accepted Answer

对于java中的32位整数..

public int swapOddEvenbits(int x)
{
   return (  ((x & 0xaaaaaaaa) >> 1 | ((x & 0X55555555) << 1) );

}

如果您使用的是 64 位，则需要更改掩码..

score 0 · Accepted Answer

由于一个字节中只有 256 种可能的组合，因此在连续执行速度比初始预计算和/或总内存利用率更重要的任何时候，这似乎是使用基于查找表的解决方案的好选择。

例如：

lookupTable[00000000] = 00000000
lookupTable[00000001] = 00000010
lookupTable[00000010] = 00000001
...

6 回答 6