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

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

Из 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 число меньше нашего.