4

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

4 ответа 4

7

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

n = log2(x+1)

log2271 = 8.082 -> 9 бит

log2521 = 9.025 -> 10 бит

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

7
  • а почему,в первый раз вы добивили 1 к 270 а 520 не добавили?
    – Павел
    12 сен 2015 в 4:52
  • @Павел опечатался
    – zenden2k
    12 сен 2015 в 4:56
  • В общем случае логарифм от количества различных чисел, которые мы хотим представить. Например, для чисел от -128 до 127 это log_2(256) = 8
    – VladD
    12 сен 2015 в 5:30
  • @VladD: мне кажется, можно быстрее это делать, просто сравнивая числа с максимальными значениями для каждого размера.
    – Nick Volynkin
    12 сен 2015 в 10:47
  • @NickVolynkin: Ну, если нам понадобится, к примеру, закодировать значения от 200 до 203, то вполне возможно использовать два бита: 200 → 00, 201 → 01, 202 → 10, 203 → 11.
    – VladD
    12 сен 2015 в 11:24
4

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

#include <iostream>

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, если число отрицательное.

3

Предварительно генерируем массив степеней двойки. 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<Object[]> 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));
    }
}

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

1
  • 1
    Это плюс )) think about data first luke, хотя вычисление бинарного логарифма на x86 по-идее - одна инструкция 12 сен 2015 в 11:01

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.