как подсчитать минимальное количество битов требуемое для десятичных чисел в бинарном коде?

#информатика #системы_счисления

как подсчитать минимальное количество битов требуемое для десятичных чисел в бинарном
коде?
Например: 270 или 520
    

Ответы

Ответ 1

Для целых чисел без знака: взять логарифм по основанию 2 и округлить в большую сторону.

n = log2(x+1)

log2271 = 8.082 -> 9 бит

log2521 = 9.025 -> 10 бит

Для представления нуля в памяти всё равно требуется хотя бы 1 бит


Ответ 2

Если уж говорить о скорости, то некоторые архитектуры (в т.ч. x86) имеют инструкцию,
которая считает количество лидирующих нулевых бит.
Компилятор GCC имеет её встроенный аналог (обёртку).

#include 

int main()
{
    std::cout << 32 - __builtin_clz( 270 ) << std::endl; // 9
    std::cout << 32 - __builtin_clz( 520 ) << std::endl; // 10

    std::cout << 32 - __builtin_clz( 511 ) << std::endl; // 9
    std::cout << 32 - __builtin_clz( 512 ) << std::endl; // 10
}


Ответ 3

Делим на 2, пока получается число большее единицы, считаем итерации, к результату
добавляем 1. Добавляем ещё 1, если число отрицательное.


Ответ 4

Предварительно генерируем массив степеней двойки. Cравниваем число со степенями из
массива, пока не найдём первое превышающее. Индекс этого числа и есть искомый размер.

Вот код и тесты:

import org.junit.Assert;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;

import java.util.Arrays;
import java.util.Collection;

@RunWith(Parameterized.class)
public class Algorithms {

    public static int[] powersOfTwo = new int[31];

    static {
        powersOfTwo[0] = 1;
        for (int power = 1; power < powersOfTwo.length; power++) {
            powersOfTwo[power] = powersOfTwo[power - 1] * 2;
        }
    }

    @Parameterized.Parameter(0)
    public int number;
    @Parameterized.Parameter(1)
    public int size;

    @Parameterized.Parameters(name = "number:{0}, size:{1}")
    public static Collection data() {
        return Arrays.asList(new Object[][]{
                {0, 1},
                {1, 1},
                {3, 2},
                {((int) Math.pow(2, 10)) - 1, 10},
                {((int) Math.pow(2, 10)), 10},
                {((int) Math.pow(2, 10)) + 1, 11},
                {Integer.MAX_VALUE, 31}
        });
    }

    public static int getSizeOf(int number) {
        for (int power = 1; power < 30; power++) {
            if (powersOfTwo[power] >= number) return power;
        }
        return 31;
    }

    @Test
    public void testSizeOf() {
        Assert.assertEquals(size, getSizeOf(number));
    }
}


Этот алгоритм должен быть быстрее, чем вычисление логарифмов или деление.