主页 讨论版 问题 名次 状态 统计

请自觉遵守比赛规则,违者严惩,不接受求情!

问题 G: 浮点运算

问题 G: 浮点运算

时间限制:1000 ms 内存限制:256 MB
提交:0 解决:0
[ 提交][ 状态][ 讨论版]

题目描述

题目压缩包(内含样例)

众所周知浮点类型是一种常用 (大嘘) 的数据类型。考虑一种有 $t$ 位有效数字,$w$ 位指数的浮点类型,则该浮点类型在存储时使用 $t + w + 1$ 个二进制位。我们从高到低列出这些位:

  • 首先是一个符号位 $s$

  • 之后是 $t$ 个有效数字位 $a_1, a_2, \cdots, a_t$

  • 最后是 $w$ 个指数位 $b_{w - 1}, b_{w - 2}, \cdots, b_0$

如果一个浮点值中 $w$ 个指数位不都是 $0$,也不都是 $1$,则它是正规的,表示如下的实数值:

$$(-1)^s \left(1 + \sum_{k=1}^t 2^{-k} a_k \right) \times 2^E$$

对于正规浮点数:

$$E = 1 - 2^{w - 1} + \sum_{k=0}^{w-1} 2^k b_k$$

如果浮点值中 $w$ 个指数位都是 $0$,则它是非正规的,表示如下的实数值:

$$(-1)^s \sum_{k=1}^t 2^{2-2^{w-1}-k} a_k$$

显然,正规浮点值的绝对值大于等于 $2^{2-2^{w-1}}$,而非正规浮点数的绝对值小于 $2^{2-2^{w-1}}$。

请注意 $+0$ 和 $-0$ 是不同的浮点值,前者的所有二进制位都是 $0$,后者 $s = 1$,其余二进制位是 $0$。 但它们表示同一个实数,即 $0$。

如果浮点值中 $w$ 个指数位都是 $1$,则它是特殊的,表示如下的非实数值:

  • 符号位为 $0$,$t$ 个有效数字位都是 $0$,则表示 $+\infty$

  • 符号位为 $1$,$t$ 个有效数字位都是 $0$,则表示 $-\infty$

  • 符号位为 $0$ 或 $1$,$a_1 = 1$,其他 $t - 1$ 个有效数字位取任何值,则表示qNaN

  • 符号位为 $0$ 或 $1$,$a_1 = 0$,其他 $t - 1$ 个有效数字位取任何值,则表示sNaN

将 $+\infty$ 和 $-\infty$ 统称为无穷大值。本题不考虑sNaN

现在给定一个浮点类型的参数 $t$ 和 $w$,你需要计算在该类型的浮点值上进行的若干四则运算。如果参与运算的浮点值都表示实数 (即,不是特殊浮点值),则运算规则如下:

  • 首先将两浮点值表示的实数按照实数四则运算的法则进行计算。对于除法,如果两操作数都是 $0$, 则生成qNaN作为结果,并不再进行后续步骤。如果被除数不是 $0$,但除数是 $0$, 则生成无穷大值作为结果,无穷大值的符号位是两操作数符号位的异或,并不再进行后续步骤。 对于其他实数四则运算,其结果一定存在且是实数,设这个结果为 $r$。

  • 设该浮点类型能表示的所有非负实数值的集合为 $\mathbb{F}$,令 $\mathbb{E} = {2^{(2^{w-1})}}$。 设 $d(f)$ 是使得 $2^k f$ 为整数的最小 (可能为负) 整数 $k$,例如 $d(4) = -2$。 特别地,规定 $d(0) = -2^{w-1}$。 在 $\mathbb{F} \cup \mathbb{E}$ 中寻找和 $|r|$ 最接近 (差的绝对值最小) 的数。如有并列,选择 $d(\cdot)$ 值较小的数。可以证明这样选出的符合条件的数是唯一的。将选出的数记作 $r'$。

  • 显然 $\mathbb{F} \cap \mathbb{E} = \emptyset$。如果 $r' \in \mathbb{E}$, 则结果是 $\pm \infty$。否则,结果是 $\pm r'$。

  • 确定结果的符号位。如果 $r \neq 0$,则符号位根据 $r$ 的符号确定。否则:

    • 对于乘法或除法,结果的符号位是两操作数符号位的异或。

    • 对于加法或减法,当两个 $-0$ 相加,或者一个 $-0$ 减去一个 $+0$ 时,结果的符号位是 $1$ (即结果为 $-0$),否则符号位是 $0$ (即结果为 $+0$)。

对于有特殊浮点值参与的四则运算,规则如下:

  • 只要存在一个操作数为qNaN,结果就是qNaN

  • 无穷大值和实数值或符号相同的无穷大值相加,则得到该无穷大值本身。

  • 无穷大值和符号相反的无穷大值相加得到qNaN

  • 无穷大值减去实数值或符号相反的无穷大值,则得到该无穷大值本身。

  • 无穷大值减去符号相同的无穷大值得到qNaN

  • 实数值减去无穷大值,得到一个符号相反的无穷大值。

  • 无穷大值和 $0$ 相乘得到qNaN

  • 无穷大值和无穷大值或非 $0$ 实数值相乘得到无穷大值,结果的符号位是两操作数符号位的异或。

  • 无穷大值除以无穷大值得到qNaN

  • 无穷大值除以实数值得到无穷大值,结果的符号位是两操作数符号位的异或。

  • 实数值除以无穷大值得到 $0$,结果的符号位是两操作数符号位的异或。

输入

输入第一行包含三个整数 $n$, $t$, $w$。$t$ 和 $w$ 的含义在题目描述中已经给出, $n$ 为要进行的四则运算的个数。保证 $10 \leq t$; $5 \leq w \leq 30$; $t \leq \min(2^{w - 1}, 256)$; $1 \leq n \leq 100$。

之后 $n$ 行,每行包含三个字符串,用空格分隔。第一个和第三个字符串表示操作数,符合扩展正则表达式

^(-?0x[01][.][0-9a-z]{u}p[+-](0|[1-9][0-9]*)|-?inf|nan)$

inf表示 $+\infty$,-inf表示 $-\infty$,nan表示qNaN,其他表示实数值。

对于实数值,如果开头是-表示负数 (即符号位为 $1$),否则表示正数 (即符号位为 $0$)。[01]这一部分如果为1,则表示正规浮点数,否则表示非正规浮点数。[0-9a-z]{u}中,u应替换为 $\lceil t/ 4 \rceil$。[01][.][0-9a-z]{u}这一部分是一个小数点前 $1$ 位,小数点后 $u$ 位的十六进制小数 $a$。[+-](0|[1-9][0-9]*)这一部分是一个十进制整数,即 $E$,保证 $-2^{w-1} + 2 \leq E \leq 2^{w-1} - 1$。这样表示的实数值就是 $a \cdot 2^E$。对于 $0$ 保证 $E = 0$。对于除了 $0$ 以外的非正规浮点数保证 $E = -2^{w - 1} + 2$。$E = 0$ 时保证p之后是+

将 $a$ 转换成二进制并去除小数部分末尾的若干 $0$ 后,保证小数部分至多有 $t$ 位。

第二个字符串仅有一个字符,+则表示计算加法,-表示计算减法,*表示计算乘法,/表示计算除法。

输出

对于每个四则运算输出一行,包含一个符合扩展正则表达式

^(-?0x[01][.][0-9a-z]{u}p[+-](0|[1-9][0-9]*)|-?inf|nan)$

的字符串,其含义如输入格式所给出,表示运算结果。

提示

对于样例 $1$,$t$ 和 $w$ 的取值和 TS-18661 规定的double类型一致,计算 $114.514$ 和 $1919.810$ 的和、差、积、商。

对于样例 $2$,$t$ 和 $w$ 的取值和 TS-18661 规定的float类型一致,故事背景https://bilibili.com/BV178411x7Gq

[ 提交][ 状态][ 讨论版]
Baidu
map