Как найти двоичный логарифм очень быстро? (O (1) в лучшем случае)
Там какой-либо очень быстрый метод должен найти двоичный логарифм целого числа? Например, учитывая номер x=52656145834278593348959013841835216159447547700274555627155488768 такой алгоритм должен найти y=log (x, 2), который является 215. x всегда является питанием 2.
Проблема, кажется, действительно проста. Все, что требуется, должны найти положение старшего значащего 1 бита. Существует известный метод FloorLog, но это не очень быстро специально для очень длинных целых чисел из нескольких слов.
Каков самый быстрый метод?
4 ответа
Ответ зависит от реализации или языка. Любая реализация может хранить вместе с данными количество значащих битов, так как это часто бывает полезно. Если его необходимо вычислить, найдите в этом слове самое старшее слово / конечность и самый старший бит.
Если целые числа хранятся в uint32_t a [] , то мое очевидное решение будет следующим:
Выполните линейный поиск по
a [], чтобы найти ненулевоеuint32_tзначение с наибольшим значениемa [i ]вa [](проверьте, используяuint64_tдля этого поиска, если на вашем компьютере есть собственная поддержкаuint64_t)Примените бит твидл-хаки для нахождения двоичного журнала
bзначенияuint32_ta [i], найденного на шаге 1.Вычислить
32 * i + b.
Быстрый прием: Большинство представлений чисел с плавающей запятой автоматически нормализуют значения, что означает, что они эффективно выполняют цикл Упомянутый Кристоффером Хаммарстремом аппаратно. Таким образом, простое преобразование из целого числа в FP и извлечение экспоненты должно помочь, если числа находятся в пределах диапазона экспоненты FP-представления! (В вашем случае для ввода целого числа требуется несколько машинных слов, поэтому при преобразовании потребуется выполнить несколько «сдвигов».)