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

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)

Что применимо к i) дает: 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

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

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

Answer 4

Наибольшее число, которое может быть представлено 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 ⁿ / log 2 и возьми потолок.

В последнем выражении любая база подходит для логарифмов, если обе базы одинаковы. Здесь удобно, так как нас интересует случай, когда 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 5

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

Answer 6

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

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

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

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

Answer 7

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

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

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

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

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

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

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

2^n = 999
nlog2 = log999
n ~ 10

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

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

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

Answer 9

Для двоичного числа из 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 10

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