首页 > 解决方案 > x 的值是多少,使得 x + 1 == x 和 x * 2 == x 都为真?

问题描述

标题基本上说明了一切。我的朋友给了我这个挑战,他在他正在做的一些 CTF 中解决了这个挑战。我已经考虑了一段时间,无法弄清楚。此外, INFINITY 不是一个有效的答案。谢谢。

标签: ctypesctf

解决方案


在 C 中发生这种情况的唯一方法是:

  • x是无穷大(+∞ 或 -∞)(等效地,HUGE_VAL-HUGE_VAL在不支持无穷大的实现中)。
  • x是一个 NaN,C 实现对 NaN 使用非 IEEE-754 行为。
  • x与浮点表示中的无穷大相邻,并且使用了合适的有向舍入模式。
  • x+1x*2溢出以及 C 标准未定义的结果行为恰好将比较报告为真。
  • x是未初始化的,因此是不确定的,并且在 in 的两个外观中采用不同的值,x因此x+1 == x比较为真,并且在x*2 == x类似地采用不同的值或采用零值。
  • x未初始化并具有自动存储持续时间且其地址未被占用,因此 C 标准未定义该行为,并且结果行为恰好将比较报告为真。

证明:

除了无穷大之外,这些陈述在实数中在数学上是错误的,因此这不能由实数行为引起。所以它一定是由一些非实数行为引起的,例如溢出、换行、舍入、不确定的值(在每次使用对象时可能不同)或未初始化的值。由于*被限制为具有算术操作数,我们只需要考虑算术类型。(在 C++ 中,可以定义一个类来进行比较。)

对于有符号整数,具有完全定义值的非实数行为仅在溢出时才会发生+*因此这是可能的。

对于无符号整数,具有完全定义值的非实数行为+*在有回绕时才会发生。然后,通过模M包裹,对于某个整数k,我们将有x +1 = x + kM,因此 1 = kM ,这对于包裹中使用的任何M都是不可能的。

对于该_Bool类型,对可能值的详尽测试会消除它们。

对于浮点数,具有完全定义值的非实数行为仅发生在舍入、下溢+*溢出以及 NaN 的情况下。NaN 从不按照 IEEE-754 规则进行比较,因此它们不能满足这一点,除非 C 标准不要求符合 IEEE-754,因此实现可以选择使比较为真。

x*2不会下溢,因为它会增加幅度。x+1可以使指数范围小于精度的反常浮点格式下溢,但这不会产生x+1 == x. x+1 == x可以通过四舍五入足够大来满足x,但x*2必须产生除 之外的值x

留下溢出。如果x是最大可表示有限数(因此最大可表示数小于无穷大),并且舍入模式是向下(向 -∞)或向零,x+1则将产生x并且x*2将产生x,因此比较结果为真。类似地,最大负可表示有限数将满足向上舍入(向+∞)或向零舍入的比较。


推荐阅读