ビット拡張/複製のアルゴリズムですか？

Question

ビット拡張/複製を実行する効率的な（高速の）アルゴリズムはありますか？例えば

、（24ビット値を作成）3により8ビット値の各ビットを展開：提案されている

1101 0101 => 11111100 01110001 11000111 

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

Answer 1

算術演算が何らかの理由でメモリアクセスより速い場合は、ルックアップテーブルよりも速くなる可能性があります。これは、計算がベクトル化される（PPC AltiVecまたはIntel SSE）場合、および/またはプログラムの他の部分がキャッシュメモリのすべてのビットを使用する必要がある場合に可能です。

膨張係数= 3の場合は、わずか7の命令が必要とされている：

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

または他の代替、10の命令で：他の膨張係数> = 3の場合

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

：

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ビットストリーム処理の前に値を計算する方がよい。

Answer 2

時刻に1つの入力ビットを使用できます。もちろん、ルックアップテーブルよりも遅くなりますが、テーブルのための十分なスペースがない小さな8ビットマイクロコントローラ用の書き込みを行う場合は、できるだけ小さなROMフットプリントが必要です。