算法位扩展/复制？ [英] Algorithm for bit expansion/duplication?

问题描述

有没有将执行位扩展/复制一个高效（快速）算法？

Is there an efficient (fast) algorithm that will perform bit expansion/duplication?

例如，展开每个位在8位值由3（创建一个24位值）：

For example, expand each bit in an 8bit value by 3 (creating a 24bit value):

1101 0101 => 11111100 01110001 11000111

这已经提出的蛮力的方法是创建一个查找表。在未来，膨胀值可能需要的变量。即，在我们对3扩大上述例子，但可能需要通过一些其它值（多个）扩大。这就需要，我想尽量避免多次查找表。

The brute force method that has been proposed is to create a lookup table. In the future, the expansion value may need to be variable. That is, in the above example we are expanding by 3 but may need to expand by some other value(s). This would require multiple lookup tables that I'd like to avoid if possible.

推荐答案

有一个机会，使之快于查找表，如果算术计算是出于某种原因，比内存访问速度更快。如果计算矢量（PPC的AltiVec或英特尔SSE）这是可能的和/或如果该程序的其他部分需要使用超高速缓冲存储器的每个位。

There is a chance to make it quicker than lookup table if arithmetic calculations are for some reason faster than memory access. This may be possible if calculations are vectorized (PPC AltiVec or Intel SSE) and/or if other parts of the program need to use every bit of cache memory.

如果膨胀系数= 3，只需要7个指令：

If expansion factor = 3, only 7 instructions are needed:

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

或其他替代，具有10个指令：

Or other alternative, with 10 instructions:

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

有关其他扩展系数> = 3：

For other expansion factors >= 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：

Or other alternative, for expansion factors >= 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 and mask values are better to be calculated prior to bit stream processing.

这篇关于算法位扩展/复制？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！