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

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

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

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

Самым простым ответом было бы преобразовать требуемые значения в двоичные и посмотреть, сколько бит требуется для этого значения. Однако вопрос спрашивает, сколько бит для десятичного числа 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 – 1
• = 1101 ((8*1) + (4*1) + (2*0) + (1*1))

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

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

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

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

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

2^n - 1 >= 999

Прикладывая бревно к обеим сторонам,

лог(2^n - 1) >= лог(999)

лог(2^n) - лог(1) >= лог(999)

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

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

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

1. 3-значный номер

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

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

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

2^n = 999
nlog2 = log999
n ~ 10

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

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

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

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

Начиная с того, что мы знаем здесь, это числа от 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

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

Помните, что логарифмическая база 2 (n) = логарифмическая база 10 (n) / логарифмическая база 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)

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

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

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

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

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

int nBits = ceil(log2(N));

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