Я ищу эквивалент для (int) log2(X), который не страдает от проблем точности с плавающей запятой.
Я нашел несколько дискуссий по этой проблеме (как в stackoverflow, так и за ее пределами), но ни один не смогчтобы выполнить все следующие три условия:
- Переносимость: Должна быть в состоянии работать в нескольких ОС и архитектурах.
- Эффективность: лучше всего было бы постоянное время.
- Точность: не должно быть ошибок точности.
Несколько решений, которые я нашел или подумал, включают (Для временных сложностей я использую N для количества бит, а не для значения X):
- Использовать GCC
__builtin_clz.Это решение зависит от компилятора. - Используйте инструкцию
bsr.Это решение зависит от архитектуры. - Итерация по степеням 2. Это решение
O(N). - Двоичный поиск по степеням 2. Это решение
O(log(N)).Кроме того, это может привести к некоторым накладным расходам по сравнению с более простым решением. - Используйте C *
log2, чтобы получить начальное предположение и пройти из него степени 2.Я не уверен, что это решает проблему точности, но, возможно, это сработает.Тем не менее, использование значений с плавающей запятой через log2, вероятно, не сможет справиться с более простым целочисленным решением.
Возможно, я упустил некоторые аспекты предлагаемых решений, но все они сломают один из трехусловия.
Существует ли решение, которое удовлетворит все три условия?(Обратите внимание, что я не обязательно прошу о простом / простом решении, хотя это было бы предпочтительным)