Вычисление битов, необходимых для хранения десятичного числа

Question

Это домашний вопрос, с которым я застрял.

Рассмотрим целочисленное представление без знака. Сколько бит потребуется для хранения десятичного числа, содержащего:

i) 3 digits ii) 4 digits iii) 6 digits iv) n digits

Я знаю, что диапазон целого числа без знака будет от 0 до 2^n, но я не понимаю, как от этого зависит количество битов, необходимых для представления числа. Пожалуйста, помогите мне.

Заранее спасибо.

Answer 1

Ну, вам просто нужно рассчитать диапазон для каждого случая и найти наименьшую степень 2, которая выше этого диапазона.

Например, в i) 3 десятичных знака -> 10^3 = 1000 возможных чисел, поэтому вы должны найти наименьшую степень 2, превышающую 1000, которая в этом случае составляет 2^10 = 1024 (10 бит).

Редактировать: в основном вам нужно найти количество возможных чисел с количеством цифр, которые у вас есть, а затем выяснить, какое количество цифр (в другой базе, в данном случае в двоичной базе 2) имеет как минимум те же возможные числа, что и цифра. в десятичном.

Для подсчета количества возможностей дано количество цифр: possibilities=base^ndigits

Итак, если у вас есть 3 цифры в десятичном виде (основание 10), у вас есть 10^3=1000 возможности. Затем вы должны найти количество цифр в двоичном виде (биты, основание 2), чтобы число возможностей было не менее 1000, что в данном случае 2^10=1024 (9 цифр недостаточно, потому что 2^9=512 что меньше 1000).

Если вы обобщите это, у вас есть: 2^nbits=possibilities <=> nbits=log2(possibilities)

Который применяется к я) дает: log2(1000)=9.97 и так как число бит должно быть целым числом, вы должны округлить его до 10.

Answer 2

Формула для количества двоичных битов, необходимых для хранения n целых чисел (например, от 0 до n - 1):

log _e (n) / log _e (2)

и округлить.

Например, для значений от -128 до 127 (байт со знаком) или от 0 до 255 (байт без знака) число целых чисел равно 256, поэтому n равно 256, что дает 8 из приведенной выше формулы.

От 0 до n используйте n + 1 в приведенной выше формуле (есть n + 1 целое число).

На вашем калькуляторе log _e может быть просто помечен как log или ln (натуральный логарифм).

Answer 3

Наибольшее число, которое может быть представлено n- значным числом в базе b, равно bⁿ - 1. Следовательно, наибольшее число, которое может быть представлено в N двоичных цифрах, равно 2^N - 1. Нам нужно наименьшее целое число N, такое что:

2^N - 1 ≥ bⁿ - 1
⇒ 2^N ≥ bⁿ

Взяв логарифм по основанию 2 обеих сторон последнего выражения, получим:

log₂ 2^N ≥ log₂ bⁿ
⇒ N ≥ log₂ bⁿ
⇒ N ≥ log bⁿ / log 2

Поскольку мы хотим, чтобы наименьшее целое число N, удовлетворяющее последнему отношению, нашло N, найдите log bⁿ / log2 и возьмите потолок.

В последнем выражении любая основа подходит для логарифмов, если обе базы одинаковы. Здесь удобно, поскольку нас интересует случай, когда b = 10, использовать логарифмы с основанием 10, используя преимущество log₁₀10ⁿ == n.

Для n = 3:

N = ⌈3 / log₁₀ 2⌉ = 10

Для n = 4:

N = ⌈4 / log₁₀ 2⌉ = 14

Для n = 6:

N = ⌈6 / log₁₀ 2⌉ = 20

И вообще, для n десятичных цифр:

N = ⌈n / log₁₀ 2⌉

Answer 4

Хорошо, чтобы обобщить технику того, сколько битов, которые вам нужно представить для представления числа, делается таким образом. У вас есть R символов для представления, и вы хотите узнать, сколько битов, решите это уравнение R=2^n или log2(R)=n. Где n - количество битов, а R - количество символов для представления.

Для десятичной системы счисления R=9, поэтому мы решаем 9=2^n, ответ равен 3,17 бита на десятичную цифру. Таким образом, для трехзначного числа потребуется 9,51 бит или 10. Для 1000-значного числа требуется 3170 бит

Answer 5

Продолжайте делить число на 2, пока не получите коэффициент 0.

Answer 6

Короткий ответ:

int nBits = ceil(log2(N));

Это просто потому, что pow(2, nBits) немного больше N.

Answer 7

Предполагая, что вопрос заключается в том, какие минимальные биты необходимы для хранения

1. Трехзначный номер

Мой подход к этому вопросу будет:

• какое максимальное количество трехзначных чисел нам нужно хранить? Ответ: 999
• какое минимальное количество битов требуется для хранения этого числа?

Эту проблему можно решить таким образом, рекурсивно разделив 999 на 2. Тем не менее, проще использовать силу математики, чтобы помочь нам. По сути, мы решаем n для уравнения ниже:

2^n = 999
nlog2 = log999
n ~ 10

Вам понадобится 10 бит для хранения трехзначного числа.

Используйте аналогичный подход для решения других подвопросов!

Надеюсь это поможет!

Answer 8

Для двоичного числа из n цифр максимальное десятичное значение, которое оно может содержать, будет

2^n - 1, а 2 ^ n - это общие перестановки, которые можно сгенерировать, используя эти много цифр.

Возьмем случай, когда вам нужны только три цифры, т.е. ваш случай 1. Мы видим, что требования

2 ^ n - 1>= 999

Применяя журнал для обеих сторон,

log (2 ^ n - 1) >= log(999)

log (2 ^ n) - log (1) >= log(999)

n = 9,964 (приблизительно).

Принимая значение ceil n, так как 9.964 не может быть действительным числом цифр, мы получаем n = 10.

Answer 9

Здесь много ответов, но я добавлю свой подход, так как я нашел этот пост, работая над той же проблемой.

Начнем с того, что мы знаем здесь, число от 0 до 16.

Number           encoded in bits         minimum number of bits to encode
0                000000                  1
1                000001                  1
2                000010                  2
3                000011                  2
4                000100                  3
5                000101                  3
6                000110                  3
7                000111                  3
8                001000                  4
9                001001                  4
10               001010                  4
11               001011                  4
12               001100                  4
13               001101                  4
14               001110                  4
15               001111                  4
16               010000                  5

глядя на перерывы, он показывает эту таблицу

number <=       number of bits
1               0
3               2
7               3
15              4

Итак, как нам теперь вычислить шаблон?

Помните, что log base 2 (n) = log base 10 (n) / log base 10 (2)

number    logb10 (n)   logb2 (n)   ceil[logb2(n)] 
1         0            0           0           (special case)
3         0.477        1.58        2
7         0.845        2.807       3  
8         0.903        3           3           (special case)
15        1.176        3.91        4
16        1.204        4           4           (special case)
31        1.491        4.95        5
63        1.799        5.98        6

Теперь желаемый результат соответствует первой таблице. Обратите внимание, что некоторые значения также являются особыми случаями. 0 и любое число, которое является степенью 2. Эти значения не изменяются при применении потолка, поэтому вы должны добавить 1, чтобы получить минимальную длину поля битов.

Для учета особых случаев добавьте один к входу. Результирующий код, реализованный на python:

from math import log
from math import ceil
def min_num_bits_to_encode_number(a_number):
    a_number=a_number+1  # adjust by 1 for special cases

    # log of zero is undefined
    if 0==a_number:
        return 0
    num_bits = int(ceil(log(a_number,2)))  # logbase2 is available
    return (num_bits)

Answer 10

Самый простой ответ - преобразовать требуемые значения в двоичные и посмотреть, сколько битов требуется для этого значения. Однако возникает вопрос, сколько битов для десятичного числа X цифр. В этом случае кажется, что вы должны выбрать самое высокое значение с цифрами X, а затем преобразовать это число в двоичное.

В качестве базового примера, давайте предположим, что мы хотели сохранить однозначное основание из десяти чисел и хотели узнать, сколько битов потребуется. Наибольшее однозначное число из десяти основных чисел равно 9, поэтому нам нужно преобразовать его в двоичный файл. Это дает 1001, который имеет в общей сложности 4 бита. Этот же пример может быть применен к двузначному числу (с максимальным значением 99, которое преобразуется в 1100011). Чтобы найти n цифр, вам, вероятно, нужно решить другие и найти шаблон.

Чтобы преобразовать значения в двоичные, вы несколько раз делитесь на два, пока не получите коэффициент 0 (и все ваши остатки будут равны 0 или 1). Затем вы меняете порядок остатков, чтобы получить число в двоичном виде.

Пример: 13 в двоичном.

• 13/2 = 6 р 1
• 6/2 = 3 р 0
• 3/2 = 1 р 1
• 1/2 = 0 r 1
• = 1101 ((8 * 1) + (4 * 1) + (2 * 0) + (1 * 1))

Надеюсь, это поможет.

Answer 11

Как сказано выше, краткий (идеальный и блестящий) ответ от абсурда таков:

N = ⌈n / log₁₀ 2⌉

Более быстрый ответ может быть:

N < ( n × 3402 ) » 10 + 1

« » » означает побитовый сдвиг вправо, который представляет собой деление на степень 2, округленное вниз.

Эта формула требует только целочисленных операций и дает хороший результат до довольно большого количества цифр (более 1000, а ошибка равна 0 или +1). Его можно использовать для выделения буфера в анализаторе, поскольку ошибка всегда положительна.

Пояснение:
Сначала превратим деление в умножение:

N = n / журнал ₁₀ 2 = n × ( 1/log₁₀ 2 )

Давайте умножим на степень 2 и выберем целую верхнюю границу:

n × ( 1/log₁₀ 2 ) × 2¹⁰ = n × 3401,654… < n × 3402

Затем разделите на 2 ¹⁰ :

n / log₁₀ 2 < ( n × 3402 ) / 2¹⁰
N < ( n × 3402 ) / 2¹⁰

Наконец, замените деление на сдвиг и добавьте 1, чтобы округлить вверх.

n/log₁₀ 2 < ( n × 3402 ) » 10 + 1

Вы можете легко добиться большей точности, увеличив степень 2. При 2 ¹⁶ или 2 ³² вам просто нужно отбросить младшие байты. Но вам нужны целые слова большего размера. 2⁸ может быть хорошим приближением для встраиваемых вычислений.

Answer 12

Пусть его требуемый бит n затем 2^n=(основа)^ цифра, а затем взять журнал и считать №. для п

Answer 13

Этот работает!

floor(loge(n) / loge(2)) + 1

Чтобы включить отрицательные числа, вы можете добавить дополнительный бит, чтобы указать знак.

floor(loge(abs(n)) / loge(2)) + 2