4

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

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

7 ответов 7

8

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

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

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

8
  • 2
    А вот это по настоящему правильный ответ. Видимо все остальные (включая меня) просто забыли элементарную математику. С другой стороны, автор пишет: ... вариант экономнее, так как выполняется это при рендеринге ... -- Поэтому, @Ni55aN, может быть Вам стоит поизмерять время работы разных вариантов?
    – avp
    24 окт 2014 в 9:24
  • @avp поизмерял, удивительным образом код var i=0,z=Math.ceil(A); while(z>>>=1) i++; console.log(Math.pow(2,i)); справляется со своей задачей менее чем за 1 ms, в то время, как по этому ответу колеблется от 0 до 3 ms
    – Ni55aN
    24 окт 2014 в 9:29
  • @Ni55aN, а язык-то (и ОС) какой? Ну, и от того, как и что именно измерять, результат тоже зависит... Вообще, я не верю в достоверность миллисекуных измерений (например, в Linux квант планировщика 10 ms).
    – avp
    24 окт 2014 в 10:09
  • 1
    Вообще-то, для правильного профилирования нужно * «прогреть» код (запустить его один раз, чтобы нужные функции подгрузились с диска и попали в кэш процессора, для .NET/Java ещё и JIT выполнится) * запустить его в цикле большое количество раз, не менее 1000, * убедиться, что параметры не могут быть предсказаны оптимизатором, и что результат не игнорируется (можно, например, суммировать результат и выводить на консоль после пробега теста), чтобы оптимизатор не выкинул его вычисление * не забыть поделить суммарное время пробега на количество циклов
    – VladD
    24 окт 2014 в 10:31
  • 1
    Для javascript'а jsperf.com/log-speed для больших A логарифм выигрывает в V8-браузерах, во всех остальных случаях (малые А, другие браузеры) выигрывает код @Ni55aN. Удивительно, что новый метод Math.log2, из драфта проигрывает отношению логарифмов чуть больше чем полностью. Для других языков есть быстрые вычисления логарифмов по основанию 2. Там может будет, видимо, зависеть от абсолютной величины А: O(1) может быть как больше O(lnA) так и меньше. 24 окт 2014 в 11:36
3

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

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

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

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

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

6
  • так и делал, но опять же = условный оператор, хотя... наверное, без него никак
    – Ni55aN
    23 окт 2014 в 19:36
  • @Ni55aN пока загружалось сообщение, пришла ещё одна мысль, обновил ответ... 23 окт 2014 в 19:56
  • Спасибо, вот что получилось: var i=0,z=Math.ceil(A); while(z>>>=1) i++; console.log(Math.pow(2,i));
    – Ni55aN
    23 окт 2014 в 20:02
  • 1
    В gcc искомый ответ для float x: (1 << ((int)sizeof(int) * CHAR_BIT - __builtin_clz((int)x) - 1)) (для остальных можно поискать здесь или см. комментарий @VladD).
    – avp
    23 окт 2014 в 20:16
  • @avp: FLT_MAX ~2**128 поэтому int, long long не подходят в общем случае. unsigned __int128 можно использовать на некоторых системах с gcc.
    – jfs
    25 окт 2014 в 2:25
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х машинах:

  1. Celeron(R) Dual-Core CPU T3100 @ 1.90GHz
  2. 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

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

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

2
  • 2
    @Etki: Округлить до целого, а там что-то из этого.
    – VladD
    23 окт 2014 в 18:50
  • @VladD: Если число между −½ и ½, то идея явно неудачная. 26 авг 2015 в 17:10
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
  • Почему не может? Формат float (IEEE 754) используется везде, кроме совсем уж экзотических платформ.
    – VladD
    11 ноя 2015 в 20:32
  • @VladD В процессе написания программы мне довелось столкнуться со следующими явлениями: 1) двоичный порядок константы 0.5 оказался равным 0b111111, а мантисса - нулевой; 2) число с порядком 0b11111111 при использовании процедуры unpack() вызвало ошибку. При этом никаких сомнений, что рамки указанного Вами стандарта были соблюдены с лихвой. 11 ноя 2015 в 22:32
1

В нормализованном внутреннем битовом представлении заданного числа обнулить все разряды мантиссы, кроме первого.
Если порядок пишется в допкоде, то для этого достаточно логически умножить внутреннее представление числа на внутреннее представление константы 0.5 или 0.25, в зависимости от способа представления числа.
Минус предложения - отсутствие универсальности.

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

4
  • Я только предложил идею. Как таковой задачи не было.))
    – myduomilia
    23 окт 2014 в 21:12
  • А, понял. Остроумно. Вам только надо печатать не сам индекс, а элемент массива по этому индексу.
    – VladD
    23 окт 2014 в 21:13
  • Люди предлагали таблицы - это ничто иное как массивы. Индекс оставил, так как не знаю, больший или меньший элемент все-таки надо брать.
    – myduomilia
    23 окт 2014 в 21:14
  • @myduomilia: Исходя из примера в вопросе, меньший.
    – VladD
    24 окт 2014 в 19:34

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.