比特扩展/复制算法？

Question

是否存在执行位扩展/复制的高效(快速)算法？

例如,将8位值中的每个位扩展3(创建24位值):

1101 0101 => 11111100 01110001 11000111

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

Answer 1

如果算术计算由于某种原因比内存访问更快,则有可能使其比查找表更快.如果计算是矢量化的(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在比特流处理之前更好地计算值.