6

ビット拡張/複製を実行する効率的な (高速) アルゴリズムはありますか?

たとえば、8 ビット値の各ビットを 3 で拡張します (24 ビット値を作成します)。

1101 0101 => 11111100 01110001 11000111

提案されている強引な方法は、ルックアップ テーブルを作成することです。将来的には、拡張値を可変にする必要があるかもしれません。つまり、上記の例では 3 ずつ拡張していますが、他の値で拡張する必要がある場合があります。これには、可能であれば避けたい複数のルックアップ テーブルが必要になります。

4

2 に答える 2

8

何らかの理由で算術計算がメモリ アクセスより速い場合は、ルックアップ テーブルよりも速くなる可能性があります。これは、計算がベクトル化されている場合 (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値は、ビット ストリーム処理の前に計算することをお勧めします。

于 2012-01-28T08:54:21.550 に答える
1

一度に 1 入力ビットずつ行うことができます。もちろん、ルックアップ テーブルよりも遅くなりますが、テーブル用の十分なスペースがない小さな 8 ビット マイクロコントローラーの書き込みなどを行う場合は、可能な限り最小の ROM フットプリントを持つ必要があります。

于 2012-01-26T21:37:47.237 に答える