как рассчитать log n (base r) за O (1) раз через программу c

Question

Я не могу найти O (1) способ найти журнал n с любой базой

, даже если вы можете определить O (1) временной способ для вычисления логарифма n с основанием 2, было бы спасибо полностью. ссылка, с которой я столкнулся, это http://geeksforgeeks.org/?p=10879 (пожалуйста, прочитайте комментарии к этому). они говорят, чтобы вычислить количество нулей перед числом, но как это можно сделать за O (1) время ... Я снова воспользовался помощью этого сайта, ссылка на который Как найти лидирующее число нулей в числе, используя C но O (1) является большой проблемой для меня. любая помощь будет высоко ценится.

Answer 1

Вы не можете сделать это в O (1) для сколь угодно больших чисел.Вам нужно хотя бы O (log (n)), чтобы посмотреть двоичное представление числа один раз.

Если вы установите ограничение на значение n (например, 64 бита), тогда everything выполнимо в O (1)!О-нотация не будет иметь никакого реального смысла в этом случае.

Answer 2

Если я правильно понял, вы просто хотите вычислить лог числа n в базе b. В этом случае используйте функцию log():

log(n)/log(b)

Answer 3

В зависимости от вашего процессора и вашего компилятора вы можете получить log2 в O (1) для целых чисел.Посмотрите ответы этого этого вопроса , например.Поиск самого левого бита двоичного числа аналогичен log2.