Най-близкото кратно на степен две дробни

Ако искате да изберете степента на две, най-простият начин е да умножите по напр. 16, закръглете до най-близкото цяло число, след което разделете на 16. Имайте предвид, че делението на степен две е точно, ако резултатът е нормално число. Това може да причини грешка при закръгляване за числа, които са под нормите.

Ето примерна програма, използваща тази техника:

public class Test {
  public static void main(String[] args) {
    System.out.println(roundToPowerOfTwo(0.44, 2));
    System.out.println(roundToPowerOfTwo(0.44, 3));
    System.out.println(roundToPowerOfTwo(0.44, 4));
    System.out.println(roundToPowerOfTwo(0.44, 5));
    System.out.println(roundToPowerOfTwo(0.44, 6));
    System.out.println(roundToPowerOfTwo(0.44, 7));
    System.out.println(roundToPowerOfTwo(0.44, 8));
  }

  public static double roundToPowerOfTwo(double in, int power) {
    double multiplier = 1 << power;
    return Math.rint(in * multiplier) / multiplier;
  }
}

Изход:

0.5
0.5
0.4375
0.4375
0.4375
0.4375
0.44140625

Ако въпросът е за закръгляване на което и да е число до предварително определена двоична точност, това, което трябва да направите, е следното:

1. Преобразувайте стойността в long с помощта на 'Double .doubleToLongBits()`
2. Проверете експонентата: ако е твърде голяма (exponent+required precision>51, броят на битовете в значимото), няма да можете да правите каквото и да е закръгляване, но няма да ви се налага: числото вече отговаря на вашите критерии.
3. Ако от друга страна exponent+required precision<0, резултатът от закръглянето винаги е 0.
4. Във всеки друг случай погледнете значимото и изтрийте всички битове, които са под exponent+required precisionтия значим бит.
5. Преобразувайте числото обратно в двойно с помощта на Double.longBitsToDouble()

Постигането на това правилно във всички ъглови случаи е малко трудно. Ако трябва да реша подобна задача, обикновено започвам с наивна реализация, за която мога да бъда почти сигурен, че ще е правилна, и едва след това започвам да внедрявам оптимизирана версия. Докато правя това, винаги мога да сравня с наивния подход, за да потвърдя резултатите си.

Наивният подход е да започнем с 1 и да го умножим / разделим с / по 2, докато поставим в скоби абсолютната стойност на входа. След това ще изведем по-близката от границите. Всъщност е малко по-сложно: ако стойността е NaN или безкрайност, тя изисква специално третиране.

Ето кода:

public static double getClosestPowerOf2Loop(final double x) {
    final double absx = Math.abs(x);
    double prev = 1.0;
    double next = 1.0;
    if (Double.isInfinite(x) || Double.isNaN(x)) {
        return x;
    } else if (absx < 1.0) {
        do {
            prev = next;
            next /= 2.0;
        } while (next > absx);
    } else if (absx > 1.0) {
        do {
            prev = next;
            next *= 2.0;
        } while (next < absx);
    }
    if (x < 0.0) {
        prev = -prev;
        next = -next;
    }
    return (Math.abs(next - x) < Math.abs(prev - x)) ? next : prev;
}

Надявам се, че кодът ще бъде ясен без допълнителни обяснения. От Java 8 можете да използвате !Double.isFinite(x) като заместител на Double.isInfinite(x) || Double.isNaN(x).

Да видим за оптимизирана версия. Както вече предложиха други отговори, вероятно трябва да разгледаме битовото представяне. Java изисква стойностите с плаваща запетая да бъдат представени с помощта на IEE 754. В този формат числата с double (64 бита) точност се представят като

• 1 битов знак,
• 11 бита показател и
• 52 бита мантиса.

Отново ще използваме специални случаи на NaN и безкрайности (които са представени от специални модели на битове). Има обаче още едно изключение: най-значимият бит на мантисата е имплицитно 1 и не се намира в модела на битовете – с изключение на много малки числа, където има т. нар. субнормален използваното от нас представяне, където най-значимата цифра не е най-значимият бит от мантисата. Следователно, за нормални числа ние просто ще зададем всички битове на мантисата на 0, но за субнормални, ние го преобразуваме в число, където не се запазва нито един, освен най-значимият 1 бит. Тази процедура винаги се закръгля към нула, така че за да получим другата граница, просто умножаваме по 2.

Нека видим как всичко това работи заедно:

public static double getClosestPowerOf2Bits(final double x) {
    if (Double.isInfinite(x) || Double.isNaN(x)) {
        return x;
    } else {
        final long bits = Double.doubleToLongBits(x);
        final long signexp = bits  & 0xfff0000000000000L;
        final long mantissa = bits & 0x000fffffffffffffL;
        final long mantissaPrev = Math.abs(x) < Double.MIN_NORMAL
            ? Long.highestOneBit(mantissa)
            : 0x0000000000000000L;
        final double prev = Double.longBitsToDouble(signexp | mantissaPrev);
        final double next = 2.0 * prev;
        return (Math.abs(next - x) < Math.abs(prev - x)) ? next : prev;
    }
}

Отбелязвам, че съм напълно сигурен, че съм покрил всички ъглови случаи, но следните тестове се изпълняват:

public static void main(final String[] args) {
    final double[] values = {
        5.0, 4.1, 3.9, 1.0, 0.0, -0.1, -8.0, -8.1, -7.9,
        0.9 * Double.MIN_NORMAL, -0.9 * Double.MIN_NORMAL,
        Double.NaN, Double.MAX_VALUE, Double.MIN_VALUE,
        Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY,
    };
    for (final double value : values) {
        final double powerL = getClosestPowerOf2Loop(value);
        final double powerB = getClosestPowerOf2Bits(value);
        System.out.printf("%17.10g  -->  %17.10g  %17.10g%n",
                          value, powerL, powerB);
        assert Double.doubleToLongBits(powerL) == Double.doubleToLongBits(powerB);
    }
}

Изход:

      5.000000000  -->        4.000000000        4.000000000
      4.100000000  -->        4.000000000        4.000000000
      3.900000000  -->        4.000000000        4.000000000
      1.000000000  -->        1.000000000        1.000000000
      0.000000000  -->        0.000000000        0.000000000
    -0.1000000000  -->      -0.1250000000      -0.1250000000
     -8.000000000  -->       -8.000000000       -8.000000000
     -8.100000000  -->       -8.000000000       -8.000000000
     -7.900000000  -->       -8.000000000       -8.000000000
 2.002566473e-308  -->   2.225073859e-308   2.225073859e-308
-2.002566473e-308  -->  -2.225073859e-308  -2.225073859e-308
              NaN  -->                NaN                NaN
 1.797693135e+308  -->   8.988465674e+307   8.988465674e+307
 4.900000000e-324  -->   4.900000000e-324   4.900000000e-324
        -Infinity  -->          -Infinity          -Infinity
         Infinity  -->           Infinity           Infinity

Какво ще кажете за ефективността?

Изпълних следния бенчмарк

public static void main(final String[] args) {
    final Random rand = new Random();
    for (int i = 0; i < 1000000; ++i) {
        final double value = Double.longBitsToDouble(rand.nextLong());
        final double power = getClosestPowerOf2(value);
    }
}

където getClosestPowerOf2 трябва да бъде заменено с getClosestPowerOf2Loop или getClosestPowerOf2Bits. На моя лаптоп получавам следните резултати:

• getClosestPowerOf2Loop: 2,35 сек
• getClosestPowerOf2Bits: 1,80 сек

Наистина ли си заслужаваше усилието?

Ще ви трябва малко магия, ако ще закръгляте до произволни степени на 2.

Ще трябва да проверите експонентата:

int exponent = Math.getExponent(inexact);

Тогава знаейки, че има 53 бита в мантисата, можете да намерите бита, с който трябва да закръглите.

Или просто направете:

Math.round(inexact* (1l<<exponent))/(1l<<exponent)

Използвам Math.round, защото очаквам да е оптимален за задачата, вместо да се опитвам да го внедря сам.

Ето първия ми опит за решение, което не обработва всички случаи в отговора на @biziclop и вероятно прави „под“ вместо „кръг“

public static double round(double d, int precision) {
  double longPart = Math.rint(d);
  double decimalOnly = d - longPart;
  long bits = Double.doubleToLongBits(decimalOnly);

  long mask = -1l << (54 - precision);

  return Double.longBitsToDouble(bits & mask) + longPart;
}