#алгоритм #математика #битовые_операции
Из float A, которое может принимать любое значение, нужно получить число, кратное 2n.
Например, если A = 345.53;, то результат должен быть равен 256.
Пока что в голову ничего, кроме использования условного оператора, не приходит, но
это не совсем подходит, но думаю, есть вариант экономнее, так как выполняется это при
рендеринге, что и не должно влиять на fps.
Ответы
Ответ 1
Простое решение "в лоб" на C (для сравнения скорости):
#include
#include
int main() {
volatile double A=345.53;
volatile double r;
for(int i=100000000; i--;) r= exp2(floor(log2(A)));
printf("%f\n", r);
}
volatile поставил чтобы было честное вычисление, а не результат спрогнозированный
оптимизатором.
Проверил на 2х машинах:
Celeron(R) Dual-Core CPU T3100 @ 1.90GHz
Intel(R) Core(TM) i5-2500K CPU @ 3.30GHz
Время счёта 17.812 и 9.288 секунд соответственно.
Быстрый переносимый вариант (только тело цикла):
int exp;
frexp(A, &exp);
r= ldexp(.5, exp);
Время счёта 6.240 и 1.768 секунды.
Вариант зависимый от представления в расчёте на то, что FLT_RADIX==2:
r= scalbln(1, ilogb(A));
Последний вариант у меня оказался на селероне немного медленнее -- 7.488 секунд,
а на коре немного быстрее -- 1.204 секунды.
Ответ 2
Степень двойки:
(long) (log(A)/log(2));
Ну и для малых степеней используем сдвиг, да.
Просто "float A" должно натолкнуть на мысль, что FLT_MAX ≈ 3.4E+38...
Ответ 3
Как верно подметил товарищ Etki, есть битовая операция...
Приводим float к int (отбрасываем
всё, что после запятой).
Побитово проходим слева направо (с
первого или второго бита в
зависимости от unsigned или signed)
и ищем первый бит с единицей.
После этого бита зануляем все
оставшиеся биты, но если это был
последний бит, то "число"==1 (что с ним делать, вам виднее).
в данном случае нужен не "цикл", а набор констант и if'ов. можно сделать
и циклом:
Делаем массив из Х элементов
(степени двоек, Х равен количеству
битов у переменной).
Сдвигаем вправо и увеличиваем
счётчик.
Результат равен нулю? Если да, то в
счётчике хранится положение
последней единицы (если считать
справа налево), иначе повторяем
цикл.
Берём результат из массива по
массив[счётчик].
По скорости работы сложно сказать, но, вероятно, второй способ быстрее (если учесть,
что компилятор оптимизирует), но всё равно лучше затестить.
Ответ 4
Проще всего, по-моему, будет сделать таблицу степеней двойки, считать ее один раз
и в рантайме поэлементно сравнивать А со значениями таблицы. Можно чуть-чуть ускорить
процесс, предполагая ближайшее значение с помощью пары условных операторов.
Наверняка есть крышесносящее битовое решение, но я пока не вижу четкой схемы решения
в голове.
Ответ 5
function show_str4($str){
return sprintf("%b %b %b %b",ord($str[0]),ord($str[1]),ord($str[2]),ord($str[3]));
}
function get_mask(){
$c00=chr(0); $cff=chr(255);
$test = pack("f",5e-1);
$m = pack("f",25e-2);
$mask = $c00.$c00.$c00.$cff | $m; if (($mask & $test) == $test) return $mask;
$mask = $c00.$c00.$cff.$c00 | $m; if (($mask & $test) == $test) return $mask;
$mask = $c00.$cff.$c00.$c00 | $m; if (($mask & $test) == $test) return $mask;
$mask = $cff.$c00.$c00.$c00 | $m; if (($mask & $test) == $test) return $mask;
exit(1);
}
function floattoexp2($x){
$arr=unpack("f",pack("f",$x) & get_mask());
return $arr[1];
}
$x = (float)345.67;
$y=floattoexp2($x);
$x_packed = pack("f",$x);
$mask = get_mask();
$y_packed = $x_packed & $mask;
printf("x=$x y=$y
x_packed=".show_str4($x_packed)."
mask=".show_str4($mask)."
y_packed=".show_str4($y_packed));
Результаты:
x=345.67 y=256
x_packed=11000011 11010101 10101100 1000011
mask=0 0 10000000 11111111
y_packed=0 0 10000000 1000011
Суть алгоритма - в обработке внутреннего представления float-числа по маске.
Маска формируется так:
Положение байта с порядком имеет 4 варианта, проблема решена перебором.
При этом местоположение мантиссы определяется автоматически, с использованием константы
0.25.
Алгоритм не может быть рекомендован для кроссплатформенных приложений.
Ответ 6
В нормализованном внутреннем битовом представлении заданного числа обнулить все разряды
мантиссы, кроме первого.
Если порядок пишется в допкоде, то для этого достаточно логически умножить внутреннее
представление числа на внутреннее представление константы 0.5 или 0.25, в зависимости
от способа представления числа.
Минус предложения - отсутствие универсальности.
Ответ 7
public class PositionInsertToList {
public static int searchPosition(long arr[], long key){
int l = -1;
int r = arr.length;
while(l != r - 1){
int mid = (l + r ) >> 1;
if(key < arr[mid]) r = mid;
else l = mid;
}
return r;
}
public static void main(String[] args) {
long a[] = {2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384,
32768, 65536};
System.out.println(searchPosition(a, (long)345.53));
}
}
Применяем бинарный поиск. Работает за log(a.length) - двоичный логарифм. Если в массиве
32 элемента, то поиск осуществляется за 6 действий. Получаем индекс, куда бы мы вставили
наше число. В данном случае это число 8. Получается, что в этой позиции число больше
нашего, а в позиции 7 число меньше нашего.
