Узнать количество битов, необходимых для представления положительного целого числа в двоичном формате?

Что ж, вы можете просто посчитать, сколько раз вы сдвинетесь вправо, прежде чем останетесь с нулем:

int value = 11;
int count = 0;
while (value > 0) {
    count++;
    value = value >> 1;
}

Что ж, ответ довольно прост. Если у вас есть значение типа int:

int log2(int value) {
    return Integer.SIZE-Integer.numberOfLeadingZeros(value);
}

То же самое и для Лонга ...

[Edit] Если здесь проблема заключается в сокращении миллисекунд, Integer.numberOfLeadingZeros (int) достаточно эффективен, но по-прежнему выполняет 15 операций ... Расширяя разумный объем памяти (300 байт, статический), вы можете сократить его до от 1 до 8 операции, в зависимости от диапазона ваших целых чисел.

Моя Java немного ржавая, но независимый от языка ответ (если есть функция "log2" и функция "floor") будет:

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 нет беззнаковых целых чисел, так что первое if (значение ‹0) немного сомнительно. Отрицательные числа всегда устанавливают самый старший бит, поэтому, возможно, для их представления требуется полное слово. Если вам не все равно, измените это поведение.

Между прочим, чтобы обработать 64-битное целое число, замените строку if (значение ‹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 раз, также известный как 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

Этот работает для меня!

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. Кроме того, вам нужно будет подумать о том, как вы хотите учитывать знаковый бит.

Это на 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) Math.ceil((Math.log(n) / Math.log(2))

Конечно, это работает только для положительных целых чисел.