Namaran

Code daily. Without assist.

2026-10-24

exact_in_double.c

bool exact_in_double(int64_t n) {
}

int64_t の値 n を double に変換したとき、丸めが起きずに同じ値のまま表せるなら true、そうでなければ false を返す exact_in_double を書いてください。double は IEEE 754 の倍精度(binary64)とします。n は INT64_MIN から INT64_MAX までのどの値でもよく、0 は true です。

入力例 1

exact_in_double(9007199254740993)

出力例 1

false

入力例 2

exact_in_double(9007199254740994)

出力例 2

true

入力例 3

exact_in_double(INT64_MIN)

出力例 3

true
Reference
bool exact_in_double(int64_t n) {
    uint64_t m = n < 0 ? -(uint64_t)n : (uint64_t)n;
    while (m > (UINT64_C(1) << 53) && m % 2 == 0) {
        m /= 2;
    }
    return m <= (UINT64_C(1) << 53);
}

倍精度の double は、53ビットの整数(仮数)に2の累乗(指数)を掛けた形で値を持ちます。整数 m がこの形で表せるのは、m を2で割れるだけ割って残った奇数が53ビットに収まるとき、すなわち 253 未満のときです。入力例1の 253+1 は奇数で、それ以上割れないまま 253 を超えるので表せません。入力例2の 253+2 は2で割ると 252+1 になって収まるので、253 を超える整数でも表せます。参考実装のループは、m が 253 以下になるか奇数になるまで2で割ります。253 ちょうどは 1×253 と表せるので、最後の比較は <= です。int64_t の絶対値は 263 以下なので、指数の範囲が足りなくなることはありません。

符号は仮数とは別の1ビットで持つので、判定には絶対値を使います。ただし INT64_MIN の絶対値 263 は int64_t に収まらず、-n はオーバーフローして未定義動作になります。先に uint64_t へ変換してから反転すれば、計算は 264 を法として行われ、-(uint64_t)n は正しく 263 になります。263 は2で割り切っていくと1になるので、入力例3は true です。

変換した値を元の値と比べる書き方は、どちらの向きでも判定になりません。(double)n == n は、比較の前に右辺の n も double に変換されて同じ丸めを受けるので、どの n でも真になります。(int64_t)(double)n == n のほうは、INT64_MAX が丸められて 263 になったとき、それを int64_t に戻す変換が範囲外になり、未定義動作です。掲載したのは参考実装で、唯一の正解ではありません。253 以下かどうかを先に調べ、超えた分だけ下位ビットが0かを確かめる書き方もあります。