Это, вероятно, довольно просто, но чтобы спасти меня час или около того от горя, кто-нибудь скажет мне, как вы можете вычислить количество бит, необходимых для представления данного положительного целого в Java?
например. Я получаю десятичное число 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);
}
То же самое существует для Long...
[Изменить] Если проблема с бритьем в миллисекундах здесь, Integer.numberOfLeadingZeros(int) достаточно эффективен, но все же делает 15 операций... Расширяя разумный объем памяти (300 байт, статический), вы могли бы сбрить это до 1-8 операций, в зависимости от в диапазоне ваших целых чисел.
Моя Java немного ржавая, но ответ агностики на языке (если есть функция "log2" и функция "пол" ):
numberOfBits = floor(log2(decimalNumber))+1
Предполагая, что "decimalNumber" больше 0. Если это 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/wiki/Program_optimization#Quotes.
Сначала напишите программу для чтения, затем найдите, где она медленная, а затем сделайте ее быстрее. Перед и после того, как вы оптимизируете тест на изменение. Если изменение не было достаточно большим для того, чтобы сделать код менее удобочитаемым, не беспокойтесь об этом.
Взятие двоичного журнала номера будет сообщать количество бит, необходимых для его хранения.
Если вы пытаетесь избежать цикла и вам нужна скорость, вы можете использовать такой метод:
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) этими двумя:
if( value < 0 ) { value = 0; count = 64; }
if( value >= 0x7FFFFFFF ) { value >>= 32; count += 32; }
Для неотрицательных значений, вероятно, самый прямой ответ:
java.math.BigDecimal.valueOf(value).bitLength()
(Для отрицательных чисел это даст бит длиной меньше единицы, чем абсолютное значение, а не бесконечность, которую вы ожидаете от двух дополнений).
Я хотел бы добавить некоторые другие варианты, только для полноты:
1 BigInteger.valueOf(i).bitLength()
Не очень быстро. Кроме того, BigInteger.bitLength() он прослушивается и ненадежен (исправлен в Java7), так как требуется больше бит Integer.MAX_VALUE (требуется необычно большое количество входных данных!! [например, 1 сдвинутый слева Integer.MAX_VALUE раза, aka 2^Integer.MAX_VALUE]) ) результат переполнения и отрицательные числа появляются для следующих чисел 2^(2*Integer.MAX_VALUE)-2^Integer.MAX_VALUE, который является настолько высоким, что ваша голова может взорваться. Обратите внимание, что, по оценкам, вселенная содержит около 10 ^ 80 атомов; это число 2^4G (G как в Giga, 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);.
Это на C, но я подозреваю, что вы можете легко конвертировать в Java:
Найти базу данных 2 целочисленного N-бита в операциях O (lg (N))
(int) Math.ceil((Math.log(n) / Math.log(2))
Конечно, это работает только для целых положительных чисел.
Что-то вроде этого:
public static int getNumberOfBits(int N) {
int bits = 0;
while(Math.pow(2, bits) <= N){
bits++;
}
return bits;
}
Я знаю, что вы ищете способ не использовать циклы, но я чувствую, что это довольно сложно, иначе биты будут всего лишь двумя величинами числа.