2

ビットが「インターレース」された16ビット値があります。

次の順序でビットを格納する 8 つの項目 (値 0 から 3) の配列を取得したいと考えています。

  • アイテム 0: ビット 7 と 15
  • 項目 1: ビット 6 および 14
  • 項目 2: ビット 5 および 13
  • ...
  • 項目 7: ビット 0 と 8

これは簡単な解決策です：

function uninterlace(n) {
  return [((n>>7)&1)|((n>>14)&2), // bits 7 and 15
          ((n>>6)&1)|((n>>13)&2), // bits 6 and 14
          ((n>>5)&1)|((n>>12)&2), // bits 5 and 13
          ((n>>4)&1)|((n>>11)&2), // bits 4 and 12
          ((n>>3)&1)|((n>>10)&2), // bits 3 and 11
          ((n>>2)&1)|((n>> 9)&2), // bits 2 and 10
          ((n>>1)&1)|((n>> 8)&2), // bits 1 and 9
          ((n>>0)&1)|((n>> 7)&2)];// bits 0 and 8
}

これを行うためのより良い（より速い）方法を知っている人はいますか？

編集：

ノート：

  • 事前計算されたテーブルを作成することはオプションではありません。
  • アセンブラーまたは CPU 固有の最適化を使用できない
4

4 に答える 4

1

さて、アイテムごとに3つの操作があります（テスト済みで動作します）。

これはNovelocratの答えのバリエーションです。可変マスクとスライドを使用します。

function uninterlace(n) {     
     return [((n & 0x8080) + 0x3FFF) >> 14,
             ((n & 0x4040) + 0x1FFF) >> 13,
             ((n & 0x2020) + 0x0FFF) >> 12,
             ((n & 0x1010) + 0x07FF) >> 11,
             ((n & 0x0808) + 0x03FF) >> 10,
             ((n & 0x0404) + 0x01FF) >> 9,
             ((n & 0x0202) + 0x00FF) >> 8,
             ((n & 0x0101) + 0x007F) >> 7];
}
于 2009-09-27T01:04:04.600 に答える
1 
def uninterlace(n) {
    mask = 0x0101 // 0b0000_0001_0000_0001
    slide = 0x7f  // 0b0111_1111
    return [(((n >> 0) & mask) + slide) >> 7,
            (((n >> 1) & mask) + slide) >> 7,
            (((n >> 2) & mask) + slide) >> 7,
            (((n >> 3) & mask) + slide) >> 7,
            (((n >> 4) & mask) + slide) >> 7,
            (((n >> 5) & mask) + slide) >> 7,
            (((n >> 6) & mask) + slide) >> 7,
            (((n >> 7) & mask) + slide) >> 7]
}

これは、エントリごとに5つではなく4つの操作のみです。秘訣は、シフトされた値を再利用することです。を追加するとslide、関連するビットが互いに隣接して移動し、7だけシフトすると、それらが下位の位置に配置されます。の使用は+弱点かもしれません。

さらに大きな弱点は、各エントリの操作を完全に順番に実行する必要があることです。これにより、プロセッサのパイプラインに入るから出るまでに4つの命令のレイテンシが発生します。これらは完全にパイプライン化できますが、それでも多少の遅延があります。質問のバージョンは、いくつかの命令レベルの並列性を公開しており、十分な実行リソースがあれば、エントリごとに3つの命令のみのレイテンシが発生する可能性があります。

複数の抽出を組み合わせてより少ない操作にすることは可能かもしれませんが、それを行う方法はまだ見ていません。実際、インターレースはそれを困難にします。

編集：低次ビットと高次ビットを対称的に処理し、0をインターリーブして、それらを1つずつシフトオフする、2パスのアプローチ。または、結果がはるかに高速になり、より長いビット文字列にスケーラブルになります。

slidePedroごとのコメントを修正するために編集されました。私の貧弱なベースコンバージョンスキルに時間を割いて申し訳ありません。もともと0xefは、0ビットを間違った場所に置いていました。

于 2009-09-26T22:42:04.153 に答える
1

手書きのアンロール ループよりも高速ですか? 疑わしい。

-loopを使用してコードの繰り返しを少なくすることはできますがfor、実行速度は速くなりません。

于 2009-09-26T22:16:43.423 に答える
0

128 エントリに 2 を掛けた、事前に計算された小さなテーブルはどうですか?

int[128] b1 = { 2, 3, 3, .. 3};
int[128] b0 = { 0, 1, 1, .. 1};

function uninterlace(n) {
  return [(n & 0x8000) ? b1 : b0)[n & 0x80],
          (n & 0x4000) ? b1 : b0)[n & 0x40],
          (n & 0x2000) ? b1 : b0)[n & 0x20],
          (n & 0x1000) ? b1 : b0)[n & 0x10],
          (n & 0x0800) ? b1 : b0)[n & 0x08],
          (n & 0x0400) ? b1 : b0)[n & 0x04],
          (n & 0x0200) ? b1 : b0)[n & 0x02],
          (n & 0x0100) ? b1 : b0)[n & 0x01]
         ];
}

これは、シフトと加算の代わりにビット マスキングとテーブル ルックアップを使用するため、高速になる可能性があります。

于 2009-10-07T12:02:53.927 に答える