33

これはおそらくかなり基本的なことですが、1 時間ほどの苦痛を軽減するために、Java で特定の正の整数を表すのに必要なビット数を計算する方法を誰か教えていただけませんか?

たとえば、10 進数の 11 (1011) を取得します。私は答えを得る必要があります、4。

最上位ビット以外のビットをすべて 0 に設定する方法を考え出すことができれば、 >>> 答えが得られます。でも… できません。

4

14 に答える 14

30

さて、ゼロになる前に右にシフトした回数を数えることができます。

int value = 11;
int count = 0;
while (value > 0) {
    count++;
    value = value >> 1;
}
于 2009-03-25T02:26:43.907 に答える
5

ループを回避しようとして速度が気になる場合は、次のような方法を使用できます。

int value = ...;
int count = 0;
if( value < 0 ) { value = 0; count = 32; }
if( value >= 0x7FFF ) { value >>= 16; count += 16; }
if( value >= 0x7F ) { value >>= 8; count += 8; }
if( value >= 0x7 ) { value >>= 4; count += 4; }
if( value >= 0x3 ) { value >>= 2; count += 2; }
if( value >= 0x1 ) { value >>= 1; count += 1; }

Javaには符号なし整数がないため、最初のif（value <0）は少し疑わしいものです。負の数は常に最上位ビットを設定するため、負の数を表すにはおそらく完全な単語が必要です。気になる場合は、その動作を適応させてください。

ちなみに、64ビット整数を処理するには、if（value <0）行を次の2つに置き換えます。

if( value < 0 ) { value = 0; count = 64; }
if( value >= 0x7FFFFFFF ) { value >>= 32; count += 32; }
于 2009-03-25T05:44:23.120 に答える
4

負でない値の場合、おそらく最も直接的な答えは次のとおりです。

java.math.BigDecimal.valueOf(value).bitLength()

(負の数の場合、2 の補数表記から期待される無限大ではなく、絶対値よりも 1 小さいビット長になります。)

于 2009-03-25T11:21:31.607 に答える
1

完全を期すために、他の選択肢をいくつか追加したいと思います。

1 BigInteger.valueOf(i).bitLength()

あまり速くありません。さらに、それ以上のビット数が必要な場合 (非常に高い入力数が必要!! [1 回の左シフト時間、別名] など)、結果がオーバーフローし、次の数に負の数が表示されるため、BigInteger.bitLength()バグがあり、信頼性がありません (Java7 で修正済み)。、これは頭が爆発するほど高い数値です。宇宙には約 10^80 個の原子が含まれていると推定されていることに注意してください。その数は(ギガのように) です。Integer.MAX_VALUEInteger.MAX_VALUE2^Integer.MAX_VALUE2^(2*Integer.MAX_VALUE)-2^Integer.MAX_VALUE2^4GG1024*1024*1024

2

static int neededBits(int i)
{
    assert i > 0;
    int res;
    int sh;
    res = ((i > 0xFFFF) ? 1 : 0) << 4;
    i >>= res;
    sh = ((i > 0xFF) ? 1 : 0) << 3;
    i >>= sh;
    res |= sh;
    sh = ((i > 0xF) ? 1 : 0) << 2;
    i >>= sh;
    res |= sh;
    sh = ((i > 0x3) ? 1 : 0) << 1;
    i >>= sh;
    res |= sh;
    res |= (i >> 1);
    return res + 1;
}

非常に高速なソリューションですが、それでも ye olde の半分の速さです32 - Integer.numberOfLeadingZeros(i);。

于 2012-09-01T02:11:59.943 に答える
1

2 の指数に対するバイナリ検索は、ビット シフト (上位投票の回答) ソリューションよりも高速です。これは、数値が巨大 (数千の 10 進数) であり、使用可能な最大ビット数を知っていて、生成したくない場合に役立ちます。テーブル：

    int  minExpVal   = 0;
    int  maxExpVal   = 62;
    int  medExpVal   = maxExpVal >> 1;
    long medianValue = 0l;

    while (maxExpVal - minExpVal > 1) {
        medianValue = 1l << medExpVal;
        if (value > medianValue) {
            minExpVal = medExpVal;
        } else {
            maxExpVal = medExpVal;
        }
        medExpVal = (minExpVal + maxExpVal) >> 1;
    }

    return value == 1l << maxExpVal ?  maxExpVal  + 1 : maxExpVal;

ただし、先行ゼロを使用したソリューションは、依然としてはるかに高速です。

return Long.SIZE - Long.numberOfLeadingZeros(value);

ベンチマーク:

Leading zeros time is: 2 ms
BinarySearch time is: 95 ms
BitShift time is: 135 ms
于 2018-08-22T01:56:21.530 に答える
0

これは C ですが、かなり簡単に Java に変換できると思います。

O(lg(N)) 演算で N ビット整数の底 2 の対数を求める

于 2009-03-25T04:12:52.590 に答える
0

このようなものはどうですか：

public static int getNumberOfBits(int N) {
    int bits = 0;
        while(Math.pow(2, bits) <= N){
           bits++;
       }
       return bits;
}

ループを使用しない方法を探していることは承知していますが、ビットは 2 の累乗にすぎないため、そうでなければかなり難しいと思います。

于 2013-11-20T18:13:46.247 に答える
-1 
(int) Math.ceil((Math.log(n) / Math.log(2))

もちろん、これは正の整数に対してのみ機能します。

于 2009-03-25T09:46:36.920 に答える