6

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

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

1101 0101 => 11111100 01110001 11000111

已经提出的蛮力方法是创建一个查找表。将来，扩展值可能需要可变。也就是说，在上面的示例中，我们将扩展 3，但可能需要扩展一些其他值。这将需要多个查找表，如果可能的话，我想避免这些查找表。

4

2 回答 2

8

如果由于某种原因算术计算比内存访问快，则有机会使其比查找表更快。如果计算是矢量化的（PPC AltiVec 或英特尔 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值最好在比特流处理之前计算。

于 2012-01-28T08:54:21.550 回答
1

您可以一次执行一个输入位。当然，它会比查找表慢，但如果你正在为一个没有足够空间放置表格的微型 8 位微控制器编写代码，它应该具有尽可能小的 ROM 占用空间。

于 2012-01-26T21:37:47.237 回答