比特扩展/复制算法？

Question

比特扩展/复制算法？

algorithmbit-manipulationbitexpansionduplication

6

是否有一种高效（快速）的算法可以执行位扩展/复制？

例如，将8位值中的每个位扩展3次（创建24位值）：

1101 0101 => 11111100 01110001 11000111

提出的暴力方法是创建一个查找表。将来，扩展值可能需要是可变的。也就是说，在上面的例子中，我们是通过3进行扩展，但可能需要通过其他值进行扩展。如果可能的话，我希望避免使用多个查找表。

- jivany

6

如果你只处理8位值，查找表几乎肯定是最佳选择。它使用非常少的空间。你能否提供更多有关你使用情况和预期常见操作的细节？ - templatetypedef

输入是一个恒定的串行比特流。在当前需求中，每个数据块以8字节为一组到达，然后需要将每个比特扩展3倍，以便作为另一个比特流发送出去。64位输入，192位输出。未来的需求可能涉及在每个扩展的8位值之前添加“头”比特，并且当然要填充到字节边界。查找表虽然快速，但考虑到这需要经常运行，任何潜在的性能改进都将不胜感激。 - jivany

1

许多架构都有指令，可以大大加快这种计算的速度。如果您不担心破坏跨平台兼容性，利用这些指令几乎肯定是一个胜利 - 如果您正在优化某些算法上“琐碎”的东西，那么转向低级别的优化是关键。 - Kaganar

@Kaganar 同意。这是针对 PPC 嵌入式系统的，我已经看到了其他位运算的优化，但这个位扩展问题似乎并不常见。我知道比我聪明的人已经解决了这个问题。 ;) - jivany

具体的架构是什么？（嵌入式应用程序解释了为什么你对速度如此狂热 - 固定硬件上的固定预算。） - Kaganar

PPC440。目前性能不是问题...第一次实现将使用LUT方法，未来更改时将使用多个LUT以扩展到其他位数。现在这成为了一个练习，看看是否有可以使用的算法方法。 - jivany

2个回答

1

你可以一次输入一个比特位。当然，这将比查找表慢，但如果你正在为一个微型的8位微控制器编写程序而且没有足够的空间放置表格，那么它应该具有最小可能的ROM占用空间。

- comingstorm

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Evgeny Kluev · Accepted Answer

如果算术计算比内存访问快，那么有机会比查找表更快。如果计算可以向量化（PPC AltiVec或Intel SSE），并且/或者程序的其他部分需要使用缓存存储器的每一位，这种可能性就存在。

如果扩展因子=3，则只需要7条指令：

out = (((in * 0x101 & 0x0F00F) * 0x11 & 0x0C30C3) * 5 & 0x249249) * 7;

或者其他选择，使用10个指令：

out = (in | in << 8) & 0x0F00F;
out = (out | out << 4) & 0x0C30C3;
out = (out | out << 2) & 0x249249;
out *= 7;

对于其他扩展因子>=3：

unsigned mask = 0x0FF;
unsigned out = in;
for (scale = 4; scale != 0; scale /= 2)
{
  shift = scale * (N - 1);
  mask &= ~(mask << scale);
  mask |= mask << (scale * N);
  out = out * ((1 << shift) + 1) & mask;
}
out *= (1 << N) - 1;

对于扩展因子大于等于2的其他替代方案：

unsigned mask = 0x0FF;
unsigned out = in;
for (scale = 4; scale != 0; scale /= 2)
{
  shift = scale * (N - 1);
  mask &= ~(mask << scale);
  mask |= mask << (scale * N);
  out = (out | out << shift) & mask;
}
out *= (1 << N) - 1;

shift和mask的值最好在处理位流之前进行计算。