Узнать количество битов, необходимых для представления положительного целого числа в двоичном формате?
https://stackoverflow.com/questions/680002
-
22-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Вероятно, это довольно просто, но, чтобы сэкономить мне час или около того огорчений, кто-нибудь может сказать мне, как вы можете вычислить количество битов, необходимых для представления данного положительного целого числа в 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);
}
То же самое существует уже давно...
[Редактировать] Если здесь возникает проблема с сокращением миллисекунд, Integer.numberOfLeadingZeros(int) достаточно эффективен, но все равно выполняет 15 операций...Расширив разумный объем памяти (300 байт, статический), вы могли бы сократить его до 1-8 операций, в зависимости от диапазона ваших целых чисел.
Моя Java немного устарела, но ответ, зависящий от языка (если есть функция "log2" и функция "floor"), будет следующим:
numberOfBits = floor(log2(decimalNumber))+1
Предполагая, что "десятичное число" больше 0.Если оно равно 0, вам просто нужен 1 бит.
Целое число.toBinaryString(число).длина();
Боже мой...почему голоса "против"?
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 не имеет целых чисел без знака, так что сначала if( значение < 0 ) немного сомнителен.Отрицательные числа всегда устанавливают старший бит, поэтому, возможно, для их представления требуется полное слово to.Адаптируйте это поведение, если вам не все равно.
Кстати, чтобы обработать 64-разрядное целое число, замените if( значение < 0 ) сопоставьте эти два:
if( value < 0 ) { value = 0; count = 64; }
if( value >= 0x7FFFFFFF ) { value >>= 32; count += 32; }
Для неотрицательных значений, вероятно, наиболее прямым ответом является:
java.math.BigDecimal.valueOf(value).bitLength()
(Для отрицательных чисел это даст битовую длину на единицу меньше абсолютного значения, а не бесконечность, которую вы ожидали бы от обозначения дополнения two.)
Я хотел бы добавить несколько других альтернатив, просто для полноты картины:
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 как в 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);.
Двоичный поиск по экспонентам, равным 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:
Найдите логарифмическую базу 2 N-разрядного целого числа за O(lg(N)) операций
Как насчет чего-то вроде этого:
public static int getNumberOfBits(int N) {
int bits = 0;
while(Math.pow(2, bits) <= N){
bits++;
}
return bits;
}
Я знаю, что вы ищете способ не использовать циклы, но я чувствую, что в противном случае это довольно прямолинейно, поскольку биты - это всего лишь двойка в степени числа.
Это работает у меня!
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.Тем временем мы отслеживаем, на сколько битов мы отклонились влево.
Итак, в этом примере, как только i при достижении 16 значение больше 11, и таким образом мы останавливаемся.И тогда мы будем насчитывать 4 бита: 1 *2 *2 *2 *2 = 16 (=2^4).
Будьте осторожны с подписанными цифрами. При работе с числами со знаком, которые могут быть положительными или отрицательными, вам сначала придется умножить отрицательные числа на -1.Кроме того, вам нужно было бы подумать о том, как вы хотите учитывать знаковый бит.
(int) Math.ceil((Math.log(n) / Math.log(2))
Конечно, это работает только для положительных целых чисел.
