Я думаю, что нашел способ сжать double в целое число стандартным образом (это не совсем то, о чем идет речь, но это очень помогает).Во-первых, нам нужно понять, почему очевидный код не правильный.
// INCORRECT CODE
uint64_t double_to_uint64 (double x)
{
if (x < 0.0) {
return 0;
}
if (x > UINT64_MAX) {
return UINT64_MAX;
}
return x;
}
Проблема здесь в том, что во втором сравнении UINT64_MAX неявно преобразуется в double,Стандарт C не определяет точно, как работает это преобразование, он только округляется в большую или меньшую сторону до представимого значения.Это означает, что второе сравнение может быть ложным, даже если математически должно быть верно (что может произойти, когда UINT64_MAX округлено, а 'x' математически между UINT64_MAX и (double)UINT64_MAX).Таким образом, преобразование double в uint64_t может привести к неопределенному поведению в этом случае.
Удивительно, но решение очень простое.Учтите, что хотя UINT64_MAX может не быть точно представимым в double, UINT64_MAX+1, будучи степенью двойки (и не слишком большой), безусловно, так и есть.Таким образом, если мы сначала округляем ввод до целого числа, сравнение x > UINT64_MAX эквивалентно x >= UINT64_MAX+1, за исключением возможного переполнения при сложении.Мы можем исправить переполнение, используя ldexp вместо добавления одного к UINT64_MAX.При этом следующий код должен быть правильным.
/* Input: a double 'x', which must not be NaN.
* Output: If 'x' is lesser than zero, then zero;
* otherwise, if 'x' is greater than UINT64_MAX, then UINT64_MAX;
* otherwise, 'x', rounded down to an integer.
*/
uint64_t double_to_uint64 (double x)
{
assert(!isnan(x));
double y = floor(x);
if (y < 0.0) {
return 0;
}
if (y >= ldexp(1.0, 64)) {
return UINT64_MAX;
}
return y;
}
Теперь вернемся к вашему вопросу: точно ли x представимо в uint64_t?Только если он не был ни округлен, ни зажат.
/* Input: a double 'x', which must not be NaN.
* Output: If 'x' is exactly representable in an uint64_t,
* then 1, otherwise 0.
*/
int double_representable_in_uint64 (double x)
{
assert(!isnan(x));
return (floor(x) == x && x >= 0.0 && x < ldexp(1.0, 64));
}
Этот же алгоритм может использоваться для целых чисел различного размера, а также для целых чисел со знаком с незначительной модификацией.Приведенный ниже код выполняет некоторые базовые тесты версий uint32_t и uint64_t (возможно, могут быть обнаружены только ложные срабатывания), но также подходит для ручного изучения крайних случаев.
#include <inttypes.h>
#include <math.h>
#include <limits.h>
#include <assert.h>
#include <stdio.h>
uint32_t double_to_uint32 (double x)
{
assert(!isnan(x));
double y = floor(x);
if (y < 0.0) {
return 0;
}
if (y >= ldexp(1.0, 32)) {
return UINT32_MAX;
}
return y;
}
uint64_t double_to_uint64 (double x)
{
assert(!isnan(x));
double y = floor(x);
if (y < 0.0) {
return 0;
}
if (y >= ldexp(1.0, 64)) {
return UINT64_MAX;
}
return y;
}
int double_representable_in_uint32 (double x)
{
assert(!isnan(x));
return (floor(x) == x && x >= 0.0 && x < ldexp(1.0, 32));
}
int double_representable_in_uint64 (double x)
{
assert(!isnan(x));
return (floor(x) == x && x >= 0.0 && x < ldexp(1.0, 64));
}
int main ()
{
{
printf("Testing 32-bit\n");
for (double x = 4294967295.999990; x < 4294967296.000017; x = nextafter(x, INFINITY)) {
uint32_t y = double_to_uint32(x);
int representable = double_representable_in_uint32(x);
printf("%f -> %" PRIu32 " representable=%d\n", x, y, representable);
assert(!representable || (double)(uint32_t)x == x);
}
}
{
printf("Testing 64-bit\n");
double x = ldexp(1.0, 64) - 40000.0;
for (double x = 18446744073709510656.0; x < 18446744073709629440.0; x = nextafter(x, INFINITY)) {
uint64_t y = double_to_uint64(x);
int representable = double_representable_in_uint64(x);
printf("%f -> %" PRIu64 " representable=%d\n", x, y, representable);
assert(!representable || (double)(uint64_t)x == x);
}
}
}