1

整数のバイトのサイズを知りたいです。例 ：

public static void main(String[] args) throws IOException {
   int a = 256;
   System.out.println(nbBytes(a));
}

static byte nbBytes(int value) {
   byte l = 0;
   while (value != 0) {
      value >>>= 8;
      ++l;
   }
   return l;
}

それは完全に機能しますが、この計算を最適化したいです。提案はありますか？:D

4

3 に答える 3

2

ランタイム パフォーマンスを意味する場合は、次のアルゴリズム (最初に設定された最高ビットを見つける) がおそらく最速です。整数引数をエンコードするために必要なバイト数を返すように、既に変更しています。

private static final int[] DE_BRUIJN_BIT_POSITION_LUT = {
      0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
      8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
    };

public static int nbBytes2(int n) {
    n |= n >> 1;  
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return DE_BRUIJN_BIT_POSITION_LUT[((n * 0x07C4ACDD) >> 27) & 0x1f] / 8 + 1;
}

より複雑に見えますが、ループや条件付き処理がないため、最新の CPU パイプラインを最適に使用できます。

De Bruijn アルゴリズムをメソッドと比較すると、メソッドは 0x0-0xff の範囲の入力に対して約 4 倍高速です (メソッドも分岐しません)。範囲 0x100-0xfff の入力の場合、私の方法は 19 倍速く、入力 0x10000-0xffffff の場合は 28 倍速く、>0x1000000 の入力の場合は 35 倍速くなります。すべての数値は私のハードウェアで有効ですが、他のコンピューターではもちろん異なる場合があります。

于 2012-10-29T16:21:31.400 に答える
1

Java では、anintは常に 32 ビットの符号付き 2 の補数値です。たとえば、Java 仮想マシン仕様 のセクション 2.3 を参照してください。

特定の値を格納するための最小ビット数を知りたい場合は、次を使用Integer.numberOfLeadingZerosして取得できます。

int bitsNeeded = 32 - Integer.numberOfLeadingZeros(value);

その後、切り上げて必要なバイト数を取得できます。

この関数が含まれていない古いバージョンの Java を実行している場合、1.6 のソースは次のとおりです。

public static int numberOfLeadingZeros(int i) {
    if (i == 0)
        return 32;
    int n = 1;
    if (i >>> 16 == 0) { n += 16; i <<= 16; }
    if (i >>> 24 == 0) { n +=  8; i <<=  8; }
    if (i >>> 28 == 0) { n +=  4; i <<=  4; }
    if (i >>> 30 == 0) { n +=  2; i <<=  2; }
    n -= i >>> 31;
    return n;
}

これがすでに行っていることよりも効率的かどうかは、プロファイリングによってのみ判断できると思います。また、遭遇すると予想される値の分布にも依存します。

負でない値のみを処理することを期待している場合は、次のようにします。

static byte nBytes(int value) {
    if (value < (1 << 8)) return 1;
    if (value < (1 << 16)) return 2;
    if (value < (1 << 24)) return 3;
    return 4;
}

これは、ゼロを表すために 1 バイトが必要であると想定しています。負の数を処理するには、次の 2 つの論理的な選択肢があります。

  1. 常に 4 を返す
  2. 値を 2 の補数で表すために必要な最小バイト数を返します。

2 番目のケースでは、次のようにします。

static byte nBytes(int value) {
    if (value < 0) {
        if (value > Integer.MIN_VALUE) {
            value = -value;
            if (value < (1 << 7)) return 1;
            if (value < (1 << 15)) return 2;
            if (value < (1 << 23)) return 3;
        }
    } else {
        if (value < (1 << 8)) return 1;
        if (value < (1 << 16)) return 2;
        if (value < (1 << 24)) return 3;
    }
    return 4;
}
于 2012-10-29T16:01:53.633 に答える
0

これがより最適かどうかはわかりませんが、別の解決策は次のようなものです（テストされていません）：

return (byte)Math.ceil(Integer.toBinaryString(value).length()/8.0);
于 2012-10-29T16:07:02.390 に答える