Число, кратное 2^n

Question

Число, кратное 2^n

Рейтинг: 4Ответов: 5Опубликовано: 23.10.2014

Из float A, которое может принимать любое значение, нужно получить число, кратное 2ⁿ.
Например, если A = 345.53;, то результат должен быть равен 256.

Пока что в голову ничего, кроме использования условного оператора, не приходит, но это не совсем подходит, но думаю, есть вариант экономнее, так как выполняется это при рендеринге, что и не должно влиять на fps.

математика алгоритм битовые-операции

Источник: Stack Overflow на русском

Answer 1

▲ 2Принят

Простое решение "в лоб" на C (для сравнения скорости):

#include <stdio.h>
#include <math.h>
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 секунды.

Answer 2

▲ 8

Степень двойки:

(long) (log(A)/log(2));

Ну и для малых степеней используем сдвиг, да.
Просто "float A" должно натолкнуть на мысль, что FLT_MAX ≈ 3.4E+38...

Answer 3

▲ 3

Как верно подметил товарищ Etki, есть битовая операция...

Приводим float к int (отбрасываем всё, что после запятой).
Побитово проходим слева направо (с первого или второго бита в зависимости от unsigned или signed) и ищем первый бит с единицей.
После этого бита зануляем все оставшиеся биты, но если это был последний бит, то "число"==1 (что с ним делать, вам виднее).

<del> в данном случае нужен не "цикл", а набор констант и if'ов. </del> можно сделать и циклом:

Делаем массив из Х элементов (степени двоек, Х равен количеству битов у переменной).
Сдвигаем вправо и увеличиваем счётчик.
Результат равен нулю? Если да, то в счётчике хранится положение последней единицы (если считать справа налево), иначе повторяем цикл.
Берём результат из массива по массив[счётчик].

По скорости работы сложно сказать, но, вероятно, второй способ быстрее (если учесть, что компилятор оптимизирует), но всё равно лучше затестить.

Answer 4

▲ 2

Проще всего, по-моему, будет сделать таблицу степеней двойки, считать ее один раз и в рантайме поэлементно сравнивать А со значениями таблицы. Можно чуть-чуть ускорить процесс, предполагая ближайшее значение с помощью пары условных операторов.

Наверняка есть крышесносящее битовое решение, но я пока не вижу четкой схемы решения в голове.

Answer 5

▲ 2

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<br>x_packed=".show_str4($x_packed)."<br>mask=".show_str4($mask)."<br>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.

Алгоритм не может быть рекомендован для кроссплатформенных приложений.

Число, кратное 2^n

Ответы