logo标签列表

对于整数x，表达式(x == x + 1)是否总是返回false？

language-agnosticboolean-expression
10

我在一本面试准备书籍《面试算法》中看到了这个问题。但是它没有说明答案。

根据我的知识，它会返回false。我有什么遗漏吗？

3
除非你过载了operator==，否则这只是一个数学上的异常。 :) - Paul Manta
假设 'No'，否则这将是一个毫无意义的问题！ :) - Mitch Wheat
x 是在哪里声明的？它是否被多个线程更新？这是什么编程语言？ - Op De Cirkel
什么编程语言？ - Paul R
也许是检查 x 是否为空？或者，如果您的语言设置了 MAX_INTEGER 溢出，则 X 是否为 MAX_INTEGER。你能说出这个语言吗？ - RiaD
1
这在执行饱和加法的机器上可能是正确的。尽管优化器会跳过实际测试（整数溢出被视为未定义行为）。 - ruslik
7个回答
13

Javascript让我想起了一个特殊的数值，Infinity。

因此实际上这将返回true：

var x = Infinity;
alert(x == x + 1);
2
inf 考虑得当确实是明智的事情。同样适用于 Python 中的 float('inf')。 - Chris Morgan
2
但请记住，在JavaScript中，“Infinity”是一个“数字”，JavaScript没有整数类型的概念。而且，“Infinity”被实现为具有最大指数的浮点数，因此它不是整数。 - Chris Morgan
2
问题确切地说是“整数”。 - Paul R
8
使用整数，对于所有的x，都有x！= x + 1。使用浮点数，则不能保证这一点；当指数足够大时，数字1将变得微不足道并从尾数中丢失 - 最容易看到的情况是使值无限大的最大可能指数。而无限大加一仍然是无限大。但较小的指数也可以适用。
在支持运算符重载的语言中，很可能会破坏这种微不足道的数学规律。例如，在Python中，
>>> class X(object):
...    def __eq__(self, other):
...        return True
...    def __add__(self, other):
...        return self
...
>>> x = X()
>>> x == x + 1
True

除非问题中指定了类型（和实现），否则假设总是正确是不安全的。但由于已经指定为整数，您可以知道对于所有x，x！= x + 1。整数被存储为一系列位，并且加1是通过切换最后一个位然后进行进位（如果它曾经是1等）完成的，这将永远不会得到相同的结果（无论整数类型有多少位，只要大于零即可）。

继续上一个想法，“只要它大于零”，如果您恰好使用了一种希望为您节省内存并且恰好是零位（根本不使用内存！）的奇怪整数实现，那么对于它来说，x == x + 1 将为true。哦，当我说“只要它大于零”时，我想我应该包括“带溢出”； 对于没有溢出的一位整数，对于 x = 1 的情况，x + 1 将为 1，因此它将为 true 而不是 false。但我从未遇到过小于四位的整数类型。我怀疑我在闲逛。 - Chris Morgan
等等，一个比特？如果您没有使用溢出，长度为什么很重要呢？在没有溢出和错误的情况下，可以实现x + 1 == x，其中x = 2^(n-1)。 - Chris Morgan
3

它应该:)

这也适用于

x = Int32.MaxValue;
result = x == x + 1;
在哪种编程语言中？ - Paul R
好问题。我猜是.NET / C#，但你说得对，语言可能是解决方案。也许在某些情况下，特定的语言会出现意外行为。 - Boas Enkler
3
这取决于语言和运算符优先级。可能 == 运算符的优先级等于或高于 + 运算符。在这种情况下，您的表达式将扩展为 ((x == x) + 1)，这可能会导致错误（因为您正在将 1 添加到布尔值）或评估为 2（因为在许多语言中，TRUE 等于 1）。
我不知道有哪些语言中的 == 优先级等于或高于 +。
我之前遇到过一种从左到右的实现方式，没有优先级的概念，对于这种情况是成立的。不过我想不起来那是什么了。 - Chris Morgan
好的，那不是那个。我从来没有使用过它。 - Chris Morgan
3
C和C++没有定义它们的整数类型所存储的最大有符号整数值溢出时的行为。例如，类型int的最大合法值称为INT_MAX(在标准头文件中可用) - 这些语言不要求INT_MAX + 1是特定的任何内容，即它们不要求编译器或部署环境确保它仍然是INT_MAX。但出于性能原因，它们极不可能从每个算术操作生成额外的机器代码来测试溢出...相反，它们通常会让CPU对溢出做出反应并产生任意结果。
在CPU级别上，CPU没有真正的理由不检测潜在的溢出而退出，忽略一个加法或生成某种异常：如果后者没有传播到操作系统/应用程序，或者被它们忽略，则可能看到原始值。但大多数CPU对于有符号类型的"+1"与对于无符号类型的"+1"处理方式相同，而C/C++要求对于无符号类型简单地绕过模数2^#bits...然后如何将其解释为有符号数字取决于使用的有符号数字表示之一。对于一些语言和CPU，BCD值的整数运算可能是可能的 - 它们如何对溢出做出反应甚至更难以推测。
2

举个例子，在Java中，如果代码在多个线程中执行，x == x + 1可能也是正确的。

这是因为另一个线程有可能同时修改x，所以条件最终可能会变成真的。为了避免缓存，x变量必须声明为volatile。

0

当然它必须是假的，除非你按照Paul所说的去做;) x+1计算出的值比x大1。因此，例如45 == 45 + 1是错误的。在这个表达式中不会进行任何赋值。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接