2

私はJavaを使用しており、チェスエンジンをコーディングしています。

バイト内の最初の1ビットのインデックスと最後の1ビットのインデックスを見つけようとしています。

私は現在JavaでLong.numberOfTrailingZeros（）（またはそのようなもの）を使用しており、バイトを除いてその機能をエミュレートしたいと思います。

それは次のようなものでしょうか：

byte b = 0b011000101;
int firstOneBit = bitCount ((b & -b) - 1);

もしそうなら、bitCountを比較的効率的に実装するにはどうすればよいでしょうか。私は良い説明を気にしません、ただ私にコードを与えないでください。

4

4 に答える 4

3

256 エントリのルックアップ テーブルを使用します。それを作成するには：

unsigned int bitcount ( unsigned int i ) {
unsigned int r = 0;
while ( i ) { r+=i&1; i>>=1; } /* bit shift is >>> in java afair */
return r; 
}

もちろん、テーブルを初期化するために最大 256 回実行するため、これは高速である必要はありません。

于 2008-12-18T03:41:29.770 に答える
2

正解は、ほとんどすべてのプロセッサがこの種のことを行うための特別な命令を持っているということです (先頭のゼロ、末尾のゼロ、1 の数など)。x86 には bsf/bsr があり、powerpc には clz があります。うまくいけば、Integer.numberOfTrailingZeros はこれらを使用するのに十分スマートですが、Java でこの種のプラットフォーム固有の関数を使用する可能性がある唯一の方法です (使用する場合でも)。

Aggregate Magic Algorithmsは、明白な (ルックアップ テーブル) からかなり巧妙な SWAR アプローチに至るまで、この種の問題に対するいくつかのアプローチを備えた別の場所です。しかし、Java ランタイムが後者について賢い場合、それらはすべて Integer(x).numberOfTrailingZeros() に負けると思います。ボックス化を最適化し、numberOfTrailingZeros にプラットフォーム固有の手法を使用することが可能である必要があります。両方を実行すると、それが勝ちます。

完全を期すために、華麗なビット ワッキングのもう 1 つの古典的なアーカイブは、古いMIT HAKMEMコレクションです ( PDP-6/10 アセンブラーのスキルがさびてきた場合は、半近代化されたC バージョンもあります)。

于 2008-12-18T04:30:10.327 に答える
2 
/* Count Leading Zeroes */

static uint8_t clzlut[256] = {
  8,7,6,6,5,5,5,5,
  4,4,4,4,4,4,4,4,
  3,3,3,3,3,3,3,3,
  3,3,3,3,3,3,3,3,
  2,2,2,2,2,2,2,2,
  2,2,2,2,2,2,2,2,
  2,2,2,2,2,2,2,2,
  2,2,2,2,2,2,2,2,
  1,1,1,1,1,1,1,1,
  1,1,1,1,1,1,1,1,
  1,1,1,1,1,1,1,1,
  1,1,1,1,1,1,1,1,
  1,1,1,1,1,1,1,1,
  1,1,1,1,1,1,1,1,
  1,1,1,1,1,1,1,1,
  1,1,1,1,1,1,1,1,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0
};

uint32_t clz(uint32_t val)
{
  uint32_t accum = 0;

  accum += clzlut[val >> 24];
  accum += (accum == 8 ) ? clzlut[(val >> 16) & 0xFF] : 0;
  accum += (accum == 16) ? clzlut[(val >>  8) & 0xFF] : 0;
  accum += (accum == 24) ? clzlut[ val        & 0xFF] : 0;

  return accum;     
}

説明：

これは、バイトの順列ごとに先頭のゼロの数をルックアップ テーブルとして格納することによって機能します。バイト値を使用して、その値の先行ゼロの数を調べます。この例では unsigned int に対してこれを行っているため、4 つの個々のバイトをシフトしてマスクし、それに応じてルックアップを累積します。3 項ステートメントを使用して、セットされているビットが見つかるとすぐに累積を停止します。累積値が 8、16、または 24 であることは、これまでに設定されたビットが見つからなかったことを意味します。

また、一部のアーキテクチャでは、これを (命令として) ハードウェアでサポートしています。アセンブリ ニーモニックは、「CLZ」または「BSR」と呼ばれることがよくあります。これらは、それぞれ「カウント リーディング ゼロ」と「ビット スキャン リバース」の略語です。

于 2010-03-01T12:22:40.653 に答える
0

それが高速であると仮定する場合Long.numberOfTrailingZeros（つまり、利用可能な場合に単一の ASM 命令を使用するように JIT コンパイル/最適化されている場合）、次のような単純なことができないのはなぜですか。

max(8,Long.numberOfTrailingZeros(val))

ここで、val は Long に変換されたバイト値です。これも、それmax()が利用可能であり、asm select または max 命令を使用するように最適化することを前提としています。

理論的には、それをサポートするマシンでは、これらの操作を 2 つのアセンブラー命令に JIT コンパイルできます。

于 2009-02-17T21:18:40.677 に答える