Блог

Учитывая два числа с плавающей запятой, p и q где 0 < p < q я заинтересован в написании функции partition(p,q) , которая находит «простейшее» число r , которое находится между p и q . Например:

 partition(3.0, 4.1) = 4.0 (2^2)
partition(4.2, 7.0) = 6.0 (2^2   2^1)
partition(2.0, 4.0) = 3.0 (2^1   2^0)
partition(0.3, 0.6) = 0.5 (2^-1)
partition(1.0, 10.0) = 8.0 (2^3)
  

В последнем случае меня интересует наибольшее число (так что 8, а не 4 или 2).

Предположим, предположим, что p и q являются как нормализованными, так и положительными, и p < q .

Если p и q имеют разные показатели, оказывается, что искомое число — это число, полученное путем обнуления мантиссы q после ведущего (и часто неявного) 1 . Угловые случаи оставлены в качестве упражнения, особенно случай, когда q мантисса уже состоит из нулей после ведущего, возможно, неявного, 1 .

Если p и q имеют одинаковый показатель, то мы должны посмотреть на их мантиссы. Эти мантиссы имеют несколько общих битов (начиная с самого значимого конца). Давайте назовем c1 c2 .. ck pk 1 ... pn биты p мантиссы, c1 c2 .. ck qk 1 ... qn биты q мантиссы, где c1 .. ck являются общими битами и pk 1 , qk 1 отличаются. Тогда pk 1 равно нулю и qk 1 равно единице (из-за гипотез). Число с тем же показателем степени и мантиссой c1 .. ck 1 0 .. 0 находится в интервале p .. q и является искомым числом (опять же, угловые случаи оставлены в качестве упражнения).

• Запишите числа в двоичном формате (завершая, если возможно, поэтому 1 записывается как 1.0000... , а не 0.1111... ),
• Сканируйте слева направо, «сохраняя» все цифры, в которых два числа равны
• В первой цифре, где два числа отличаются, p должно быть 0 и q должно быть 1, поскольку p < q :
  • Если q после этой точки есть еще 1 цифра, затем поставьте 1 в этот момент, и все готово.
  • Если q после этой точки не более 1 цифры, то это приведет к r == q , что запрещено, поэтому вместо этого добавьте 0 цифр. Следуйте за этим цифрой 1, если это не приведет к r == p , и в этом случае добавьте еще 0, а затем 1.

По сути, мы усекаем q до первого места, в котором p и q отличаются, затем немного изменяем его, если необходимо, чтобы избежать r == p или r == q . Результат, безусловно, меньше q и больше p . Это «самый простой» (имеет наименьшее возможное количество цифр 1), поскольку любое число между p и q должно иметь общую начальную последовательность. Мы добавили к этой последовательности только одну цифру 1, что необходимо, поскольку только начальная последовательность <= p , поэтому ни одно значение в диапазоне (p,q) не имеет менее 1 цифры. Мы выбрали «наибольшее» решение, потому что мы всегда помещаем наш дополнительный 1 в первое (наибольшее) возможное место.

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