как подсчитать минимальное количество битов требуемое для десятичных чисел в бинарном коде? Например: 270 или 520
4 ответа
Для целых чисел без знака: взять логарифм по основанию 2 и округлить в большую сторону.
n = log2(x+1)
log2271 = 8.082 -> 9 бит
log2521 = 9.025 -> 10 бит
Для представления нуля в памяти всё равно требуется хотя бы 1 бит
-
-
-
В общем случае логарифм от количества различных чисел, которые мы хотим представить. Например, для чисел от -128 до 127 это log_2(256) = 8– VladD12 сен 2015 в 5:30
-
@VladD: мне кажется, можно быстрее это делать, просто сравнивая числа с максимальными значениями для каждого размера.– Nick Volynkin ♦12 сен 2015 в 10:47
-
@NickVolynkin: Ну, если нам понадобится, к примеру, закодировать значения от 200 до 203, то вполне возможно использовать два бита: 200 → 00, 201 → 01, 202 → 10, 203 → 11.– VladD12 сен 2015 в 11:24
Если уж говорить о скорости, то некоторые архитектуры (в т.ч. 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
}
Делим на 2, пока получается число большее единицы, считаем итерации, к результату добавляем 1. Добавляем ещё 1, если число отрицательное.
Предварительно генерируем массив степеней двойки. 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Это плюс )) think about data first luke, хотя вычисление бинарного логарифма на x86 по-идее - одна инструкция 12 сен 2015 в 11:01