5

1 から 64 までの int を取り、適切な「ビットマスク」を返す関数を書きたいと思います。入力と同じ数の 1 ビットがあります。

私はこのように始めました：

/** Computes a bitmaks */
private static long mask(final int bitsPerValue) {
    return (1L << bitsPerValue) - 1L;
}

しかし、64 の値が間違っていることに気付きました。

(1L << 64) - 1L == 1L - 1L == 0

今私はこれを持っています：

/** Computes a bitmaks */
private static long mask(final int bitsPerValue) {
    return (bitsPerValue == 64) ? -1 : ((1L << bitsPerValue) - 1L);
}

それはかなり醜いです。また、条件は制御フローを変更する可能性があるため、単純な算術演算よりもコストがかかります。マスクを事前に計算して静的配列に入れることもできますが、配列へのアクセスは単純な算術演算よりもコストがかかり、おそらく条件付きよりもさらに高価です。

条件なしでこれを書く合理的な方法はありますか? このコードは毎秒何億回も実行されるため、高速である必要があります。

4

3 に答える 3

5

条件なしでそれを行う方法は次のとおりです。

private static long mask(final int bitsPerValue) {
    return ((1L << bitsPerValue) - (bitsPerValue >> 6)) - 1L;
}

Javaでは、1L << bitsPerValue の最下位6ビットのみを使用しますbitsPerValue。つまり、で元の関数をbitsPerValue=64呼び出すことは、で呼び出すことと同じbitsPerValue=0です。上で提示したバージョンはそれを処理します：の場合bitsPerValue=64、式は次のようになります。

(1L - 1L) - 1L == -1L

さて、これを本当に「1秒間に数十億回」と呼ぶのであれば、条件付きのものやルックアップテーブル付きのものを含め、コードのすべてのバリアントをベンチマークするのが最善の戦略だと思います。

于 2012-01-23T11:18:39.923 に答える
3

私は試した：

long value = 0xffffffffffffffffl >>> (64 - i); // that's ef ef ef... el.

しかし、これは i = 0 で問題を引き起こしているようです。上記はcで機能します。「値」が符号なしであることを考えると、おそらく上記はJava 7で機能します。

ただし、ゼロは必要ないため、上記、つまり 1 から 64 の値で問題ありません。

于 2012-01-23T11:29:49.183 に答える
0

私見、65ビット値を持つという要件を追加するだけでは十分ではありません。値を生成するためにOR演算を使用するだけです。それほど時間はかかりません。このような：

private static long mask(final int bitsPerValue) {
  long mask = 1;
  long value = 0;
  for (int i=0; i<bitsPerValue; i++ ) {
    value = value | mask;
    mask = mask << 1;
  }
  return value;
}

静的配列を使用したくないようですが、64 * 8 バイトのメモリを使用するのが最も高速な方法です。さらに、小さなメモリフットプリントと十分な速度を同時に達成するのは簡単ではないと思います。したがって、念のため、最速のアプローチは次のようになります。

long valarray[] = new long[64];

private static long[] generateValues() {
  long mask = 1;
  long value = 0;
  for (int i=0; i<64; i++ ) {
    value = value | mask;
    mask = mask << 1;

    valarray[i] = value;
  }
  return valarray;
}

private static long[] mask(final int bitsPerValue) {
  return valarray[bitsPerValue-1];
}

もう 1 つの可能なアプローチは、最新の 64 '1 のビットの場合に BigInteger を使用することです。でも、速くて醜くないとは思いません。

于 2012-01-23T11:38:50.907 に答える