Ближайшее кратное степени двойки дроби

Если вы хотите выбрать степень двойки, самый простой способ — умножить, например, на 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;
}