Блог

Главная - Вопросы по программированию - Верно ли, что количество необходимых двоичных цифр для любого заданного положительного целого числа равно ceil( log_2 n)?

Верно ли, что количество необходимых двоичных цифр для любого заданного положительного целого числа равно ceil( log_2 n)?

#c #math #time-complexity

#c #математика #временная сложность

Вопрос:

Название в значительной степени говорит об этом. Я могу только догадываться, но у меня нет доказательств того, что это верно. В Python math.ceil(math.log(n) / math.log(2)) .

Контекст: Я создаю двоичную функцию типа intbyte-to-char *, которая отображает только необходимые цифры (без конечных нулей), поэтому мне нужно будет динамически выделять память для массива символов. Однако я предполагаю, что существует верхняя граница, которую я мог бы использовать для статического определения длины.

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

Комментарии:

1. Правильная формула: floor(log2(number)) 1

2. @2501: Фух. Вы подтверждаете удачный вывод в моем (исправленном) ответе;-)

3. @Bathsheba Как вы упомянули, это работает корректно только с неограниченной точностью.

4. Действительно. Использование floor и ceil с log — это путь к катастрофе.

5. Конечно, вам нужно: 1 floor(log2(n)) двоичные цифры для представления (n) . например, рассмотрите n = 1 ; ваша формула дает, ceil(log2(1)) которая дает вам ceil(0) , явно не логичный ответ.

Ответ №1:

Формула почти правильная, но вы будете на одну цифру меньше для точных степеней 2. Формула

1 math.floor(math.log(n) / math.log(2))

я думаю, будет работать лучше. Но я бы не стал слишком зацикливаться на этом просто потому, что я бы никогда не стал полагаться на компьютер для вычисления math.floor(math.log(n) / math.log(2)) без риска того, что результат будет на единицу меньше из-за неточности, сосредоточенной вокруг плавающей точки и вычисления a log : в последнем случае вы находитесь во власти вашего набора микросхем.

Тестирование длины путем повторного целочисленного деления на 2 до достижения нуля было бы более надежным и, возможно, более быстрым. log это не дешевая функция в вычислительном отношении. Вы могли бы даже использовать кричащую битную скрипку x amp; (x - 1) (погуглите это).

Комментарии:

1. math.ceil(math.log2(64)) = 6 . Однако для кодирования 64 требуется 7 бит. Остерегайтесь предельных случаев.

2. Тестирование путем деления на 2 до достижения нуля на самом деле намного быстрее и умнее, я думаю. Не думал об этом.

3. @AdHominem: Да, это на удивление быстро. AFAIK, даже самые современные чипсеты используют подход Ньютона-Рафсона для вычисления log , с таблицей сохраненных значений в качестве отправных точек.

Ответ №2:

У вас есть хороший ответ от @Bathsheba на вторую часть вопроса:

Мне нужно было бы динамически выделять память для массива символов. Однако я предполагаю, что существует верхняя граница, которую я мог бы использовать для статического определения длины.

Вы можете использовать snprintf (с NULL в качестве буфера и 0 в качестве максимального числа байтов) для подсчета количества символов / цифр:

 #include <stdio.h>

int main(void)
{
    size_t len = snprintf(NULL, 0, "%d", 1234)   1;
    char str = malloc(len);

    snprintf(str, len, "%d", 1234);
    puts(str);
    free(str);
    return 0;
}

Другим способом (если вы можете использовать расширения GNU) является asprintf:

 #define _GNU_SOURCE

#include <stdio.h>

int main(void)
{
    char *str;

    asprintf(amp;str, "%d", 1234);
    puts(str);
    free(str);
    return 0;
}