正の整数を 2 進数で表すのに必要なビット数を調べますか?
https://stackoverflow.com/questions/680002
-
22-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
これはおそらくかなり基本的なことですが、1 時間ほどの手間を省くために、Java で特定の正の整数を表すのに必要なビット数を計算する方法を誰か教えていただけませんか?
例えば10 進数の 11 (1011) が得られます。答えを得る必要があります、4。
最上位ビット以外のすべてのビットを 0 に設定する方法を見つけて >>> それを実行できれば、答えが得られると考えました。しかし...私はできません。
解決
さて、あなただけのあなただけのゼロが残っている前に、あなたが右にシフト回数をカウントすることができます：
int value = 11;
int count = 0;
while (value > 0) {
count++;
value = value >> 1;
}
他のヒント
さて、答えは非常に単純です。あなたはint型の値を使用している場合：
int log2(int value) {
return Integer.SIZE-Integer.numberOfLeadingZeros(value);
}
同じロングのために存在...
[編集] ミリ秒を剃ることは、ここで問題がある場合は、Integer.numberOfLeadingZeros（int）が合理的に効率的であるが、それでも15回の操作を行います...（静的300バイト）のメモリの合理的な量を拡大あなたが応じて、1〜8の操作にそれを剃ることができあなたの整数の範囲でます。
私のJavaは少し錆びですが、言語に依存しない答え（「LOG2」機能と利用できる「床」機能がある場合）になります：
numberOfBits = floor(log2(decimalNumber))+1
それが0であれば「のDecimalNumberが」0以上であると仮定すると、あなただけの1ビットを必要とします。
Integer.toBinaryString（数）.LENGTH（）;
やれやれ...なぜダウン投票？
public class Main
{
public static void main(final String[] argv)
{
System.out.println(Integer.toBinaryString(0).length());
System.out.println(Integer.toBinaryString(1).length());
System.out.println(Integer.toBinaryString(2).length());
System.out.println(Integer.toBinaryString(3).length());
System.out.println(Integer.toBinaryString(4).length());
System.out.println(Integer.toBinaryString(5).length());
System.out.println(Integer.toBinaryString(6).length());
System.out.println(Integer.toBinaryString(7).length());
System.out.println(Integer.toBinaryString(8).length());
System.out.println(Integer.toBinaryString(9).length());
}
}
出力：
1
1
2
2
3
3
3
3
4
4
ここでは種々の溶液の速度のための単純な試験であります
public class Tester
{
public static void main(final String[] argv)
{
final int size;
final long totalA;
final long totalB;
final long totalC;
final long totalD;
size = 100000000;
totalA = test(new A(), size);
totalB = test(new B(), size);
totalC = test(new C(), size);
totalD = test(new D(), size);
System.out.println();
System.out.println("Total D = " + totalD + " ms");
System.out.println("Total B = " + totalB + " ms");
System.out.println("Total C = " + totalC + " ms");
System.out.println("Total A = " + totalA + " ms");
System.out.println();
System.out.println("Total B = " + (totalB / totalD) + " times slower");
System.out.println("Total C = " + (totalC / totalD) + " times slower");
System.out.println("Total A = " + (totalA / totalD) + " times slower");
}
private static long test(final Testable tester,
final int size)
{
final long start;
final long end;
final long total;
start = System.nanoTime();
tester.test(size);
end = System.nanoTime();
total = end - start;
return (total / 1000000);
}
private static interface Testable
{
void test(int size);
}
private static class A
implements Testable
{
@Override
public void test(final int size)
{
int value;
value = 0;
for(int i = 1; i < size; i++)
{
value += Integer.toBinaryString(i).length();
}
System.out.println("value = " + value);
}
}
private static class B
implements Testable
{
@Override
public void test(final int size)
{
int total;
total = 0;
for(int i = 1; i < size; i++)
{
int value = i;
int count = 0;
while (value > 0)
{
count++;
value >>= 1;
}
total += count;
}
System.out.println("total = " + total);
}
}
private static class C
implements Testable
{
@Override
public void test(final int size)
{
int total;
final double log2;
total = 0;
log2 = Math.log(2);
for(int i = 1; i < size; i++)
{
final double logX;
final double temp;
logX = Math.log(i);
temp = logX / log2;
total += (int)Math.floor(temp) + 1;
}
System.out.println("total = " + total);
}
}
private static class D
implements Testable
{
@Override
public void test(final int size)
{
int total;
total = 0;
for(int i = 1; i < size; i++)
{
total += 32-Integer.numberOfLeadingZeros(i);
}
System.out.println("total = " + total);
}
}
}
私のマシン上の出力があります：
value = -1729185023
total = -1729185023
total = -1729185023
total = -1729185023
Total D = 118 ms
Total B = 1722 ms
Total C = 4462 ms
Total A = 5704 ms
Total B = 14 times slower
Total C = 37 times slower
Total A = 48 times slower
スピード文句あなたのそれらのために... https://en.wikipedia.org /ウィキ/ Program_optimization番号の引用はを。
そして、より速くそれを作る、それは遅いですその後、見つける、プログラムが最初に読めるように書きます。前に、あなたが変更テストを最適化した後。変更は、コードが読みにくくなっての費用のために十分な大きさではなかった場合は変更を気にしないでください。
を格納するのに必要なビット数を報告する数の2つのベースのログを取ります。
あなたはループを避けるためにしようとしているとあなたがスピードを気にした場合、あなたはこのようなメソッドを使用することができます：
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は、符号なし整数を持っていません。負の数はいつも間違いなく、最も重要なビットを設定し、それらを表現するためにするために、完全な単語を必要とします。あなたが気にしている場合、その動作を適応ます。
なお、これら二つ有する場合（値<0）の行を置き換える、64ビット整数を処理する
if( value < 0 ) { value = 0; count = 64; }
if( value >= 0x7FFFFFFF ) { value >>= 32; count += 32; }
負でない値の場合、おそらく最も直接的な答えは次のとおりです。
java.math.BigDecimal.valueOf(value).bitLength()
(負の数値の場合、2 の補数表記から期待される無限大ではなく、絶対値より 1 小さいビット長が与えられます。)
完全を期すために、他の選択肢をいくつか追加したいと思います。
1 BigInteger.valueOf(i).bitLength()
あまり速くありません。さらに、 BigInteger.bitLength() バグがあり信頼性が低いです (Java7 で修正されました)。 Integer.MAX_VALUE ビットが必要です (非常に多くの入力数が必要です!!)[1 左シフトなど Integer.MAX_VALUE 回、別名 2^Integer.MAX_VALUE]) 結果がオーバーフローし、次の結果に負の数が表示されます。 2^(2*Integer.MAX_VALUE)-2^Integer.MAX_VALUE これは頭が爆発してしまいそうなほどの数字です。宇宙には約 10^80 個の原子が含まれていると推定されていることに注意してください。その数字は 2^4G (G ギガのように、 1024*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;
}
非常に高速なソリューションですが、それでも昔の半分の速度です 32 - Integer.numberOfLeadingZeros(i);.
2の指数を超えるバイナリ検索が可能性がありますビットシフト（
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
これはCであるが、私はかなり簡単には、Javaに変換することができ疑います：
このようなことについては何ます：
public static int getNumberOfBits(int N) {
int bits = 0;
while(Math.pow(2, bits) <= N){
bits++;
}
return bits;
}
私はあなたがループを使用しないための方法を探している知っているが、ビットは数の力にちょうど2つですので、私はそれ以外の場合は、前方これはかなり海峡であると感じています。
この1は私の作品！
int numberOfBitsRequired(int n)
{
return (int)Math.floor(Math.log(n)/Math.log(2)) + 1;
}
にも負の数を含めるには、あなたは余分なビットを追加し、記号を指定するために使用することができます。
public static int numberOfBitsRequiredSigned(int n)
{
return (int)Math.floor(Math.log(Math.abs(n))/Math.log(2)) + 2;
}
また、このようにそれを行うことができます。
unsigned int value = 11;
unsigned int count = 0;
if(value > 0)
{
for(int i=1;i<value;i*=2) // multiply by two => shift one to left
{
++count;
}
}
注：パフォーマンスを向上させるために、ビットシフト演算にi*=2を回しについて、コンパイラの心配をしてみましょう。
私たちの間で視覚的な思想家の場合：
64 32 16 8 4 2 1
0 0 0 1 0 1 1 -> binary representation of decimal number 'value' = 11 (=1+2+8)
私たちは、右のi=1で始まります。
その後、我々は限りi < valueなどのために、2を乗じておきます。
一方で、我々は左に行ってきましたどのように多くのビットを追跡します。
この例では、できるだけ早くiが16に達すると値が11よりも大きいので、私たちは停止するようにします。そして、私たちはその後、4ビットを数えています。1 *2 *2 *2 *2 = 16 (=2^4)
を慎重に。の正または負でもよい符号付きの数を扱うときは、最初に-1で負の数を乗算しなければなりません。また、あなたはあなたのアカウントにサインビットをしたい方法を検討する必要があります。
(int) Math.ceil((Math.log(n) / Math.log(2))
もちろんこれだけ作品ます。
