AOJ 1628 - Floating-Point Numbers

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1628&lang=jp

解説

実装するだけ。
仮数部表現は 1 も含めた 53 bit で表現すると楽だと思う。
a を何回足せば仮数部に収まらなくなるかは簡単な式で O(1) で求まる。
それを今の値に足し、exp を 1 増やして現在の仮数部と a を 1bit 右シフトするだけ。
これを n が 0 になるか a が 0 になるまで繰り返せば O(logn) で解ける。

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    ll n;
    while(cin >> n, n) {
        ll a = 1LL << 52;
        for(int i = 51; i >= 0; --i) {
            char b; cin >> b;
            a |= (ll)(b == '1') << i;
        }

        ll ex = 0, sig = a;
        while(n > 0 && a != 0) {
            const ll cnt = min(n, ((1LL << 53) - sig + a - 1) / a);
            sig += a * cnt;
            while(sig >= 1LL << 53) {
                ex += 1;
                sig >>= 1;
                a >>= 1;
            }
            n -= cnt;
        }

        cout << bitset<64>((ex << 52) | (sig & ((1LL << 52) - 1))) << endl;
    }
}

感想

ICPC E 問題とは思えない軽実装。
もうちょっと重いのを置いてくれてもいいのよ。