быстрое вычисление целочисленного логарифма
В любом современном языке программирования во время преобразование целого типа в натуральный происходит преобразование в формат IEEE 754, со всеми вытекающими отсюда обстоятельствами.
int i = 10; <- 4 байта в двоичном формате целого числа
float f = i; <- 4 байта в формате IEEE 754
Во время такого преобразования вычисляются мантисса и экспонента числа f, которые записываются в соответствии с правилами формата IEEE 754.
Экспонента которая записывается в места соответствующие маске 0x7F800000, уже сама по себе является логарифмом по основанию 2 от ближайшей степени двойки, меньшей преобразуемого числа. Или в другой интерпретации - это позиция старшего бита в преобразуемом числе.
В языке С++ операция по выделению экспоненты для объявленного целого числа lValue, с предварительным преобразованием типа выглядит следующим образом:
long lValue = 127;
float fValue = lValue;
long e = (((*(long*)(&fValue )) & 0x7F800000) >> 23) - 127;
Этот результат выполняется почти в 3 раза быстрее известного мне метода подсчета номера старшего единичного бита (47 мсек против 110 мсек при 10^7 итерациях). http://habrahabr.ru/blogs/algorithm/93172/
Для того чтобы использовать этот результат для вычисления не целого логарифма, можно использовать разложение в функции в ряд в точке 2^e до 2го, 3го или какого нужно члена...
К сожалению языки высокого уровня типа Java или Action Script не дают доступ к битам у переменных в формате IEEE754. Поэтому такая оптимизация возможна только на низкоуровневых языках типа Це++ или ассемблера.
int i = 10; <- 4 байта в двоичном формате целого числа
float f = i; <- 4 байта в формате IEEE 754
Во время такого преобразования вычисляются мантисса и экспонента числа f, которые записываются в соответствии с правилами формата IEEE 754.
Экспонента которая записывается в места соответствующие маске 0x7F800000, уже сама по себе является логарифмом по основанию 2 от ближайшей степени двойки, меньшей преобразуемого числа. Или в другой интерпретации - это позиция старшего бита в преобразуемом числе.
В языке С++ операция по выделению экспоненты для объявленного целого числа lValue, с предварительным преобразованием типа выглядит следующим образом:
long lValue = 127;
float fValue = lValue;
long e = (((*(long*)(&fValue )) & 0x7F800000) >> 23) - 127;
Этот результат выполняется почти в 3 раза быстрее известного мне метода подсчета номера старшего единичного бита (47 мсек против 110 мсек при 10^7 итерациях). http://habrahabr.ru/blogs/algorithm/93172/
Для того чтобы использовать этот результат для вычисления не целого логарифма, можно использовать разложение в функции в ряд в точке 2^e до 2го, 3го или какого нужно члена...
К сожалению языки высокого уровня типа Java или Action Script не дают доступ к битам у переменных в формате IEEE754. Поэтому такая оптимизация возможна только на низкоуровневых языках типа Це++ или ассемблера.