Ответ 1
Хорошо, вы можете просто подсчитать, сколько раз вы сдвигаетесь прямо перед тем, как вы останетесь с нулевым значением:
int value = 11;
int count = 0;
while (value > 0) {
count++;
value = value >> 1;
}
Узнайте количество бит, необходимых для представления положительного целого числа в двоичном формате?
Это, вероятно, довольно просто, но чтобы спасти меня час или около того от горя, кто-нибудь скажет мне, как вы можете вычислить количество бит, необходимых для представления данного положительного целого в Java?
например. Я получаю десятичное число 11, (1011). Мне нужно получить ответ, 4.
Я понял, могу ли я определить, как установить все биты, отличные от самого значащего, до 0, а затем → > это, я получу свой ответ. Но... я не могу.
Ответы
Ответ 2
Ну, ответ довольно прост. Если у вас есть значение int:
int log2(int value) {
return Integer.SIZE-Integer.numberOfLeadingZeros(value);
}
То же самое существует для Long...
[Изменить] Если проблема с бритьем в миллисекундах здесь, Integer.numberOfLeadingZeros(int) достаточно эффективен, но все же делает 15 операций... Расширяя разумный объем памяти (300 байт, статический), вы могли бы сбрить это до 1-8 операций, в зависимости от в диапазоне ваших целых чисел.
Ответ 3
Моя Java немного ржавая, но ответ агностики на языке (если есть функция "log2" и функция "пол" ):
numberOfBits = floor(log2(decimalNumber))+1
Предполагая, что "decimalNumber" больше 0. Если это 0, вам просто нужно 1 бит.
Ответ 4
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.
Сначала напишите программу для чтения, затем найдите, где она медленная, а затем сделайте ее быстрее. Перед и после того, как вы оптимизируете тест на изменение. Если изменение не было достаточно большим для того, чтобы сделать код менее удобочитаемым, не беспокойтесь об этом.
Ответ 5
Взятие двоичного журнала номера будет сообщать количество бит, необходимых для его хранения.
Ответ 6
Если вы пытаетесь избежать цикла и вам нужна скорость, вы можете использовать такой метод:
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; }
Ответ 7
Для неотрицательных значений, вероятно, самый прямой ответ:
java.math.BigDecimal.valueOf(value).bitLength()
(Для отрицательных чисел это даст бит длиной меньше единицы, чем абсолютное значение, а не бесконечность, которую вы ожидаете от двух дополнений).
Ответ 8
Я хотел бы добавить некоторые другие варианты, только для полноты:
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);.
Ответ 9
Это на C, но я подозреваю, что вы можете легко конвертировать в Java:
Найти базу данных 2 целочисленного N-бита в операциях O (lg (N))
Ответ 10
(int) Math.ceil((Math.log(n) / Math.log(2))
Конечно, это работает только для целых положительных чисел.
Ответ 11
Что-то вроде этого:
public static int getNumberOfBits(int N) {
int bits = 0;
while(Math.pow(2, bits) <= N){
bits++;
}
return bits;
}
Я знаю, что вы ищете способ не использовать циклы, но я чувствую, что это довольно сложно, иначе биты будут всего лишь двумя величинами числа.