快速检查两个int32_t之间的差是否为1或0。

Question

快速检查两个int32_t之间的差是否为1或0。

5

一个直接的方法是：

uint32_t diff = abs(num1 - num2);
bool isZeroOrOne = (diff == 0 || diff == 1);

或者仅仅为了检查所有可能的情况：

int32_t diff = num1 - num2;
bool isZeroOrOne = (diff == 0 || diff == 1 || diff == -1);

有更优化的方式吗？

- mad0x60

6

(uint32_t)(num1 - num2 + 1) <= 2 - Raymond Chen

4

你确实存在性能问题吗？在对整个代码进行分析后，再开始优化。 - Pepijn Kramer

2

你的两个解决方案只对特定范围的num1和num2正确，因为它们可能会导致有符号整数溢出，或者你会取INT_MIN的绝对值 - 这两种情况都是未定义的行为。 - Paul Hankin

3

@PepijnKramer：“在对整个代码进行剖析后再开始优化”这是一个错误的建议。优化应该从设计阶段就开始，因为算法选择对性能有巨大影响。像OP所问的低级别优化可以稍后处理，但通常情况下，优化应该在整个项目中始终被考虑到。 - Eric Postpischil

2

@EricPostpischil 我坚持我的代码片段建议。但是我同意，设计很重要。但这是在接口/分解级别的设计。因此，您可以单元测试（和性能）测试各个部分（并稍后修改内部数据结构/算法）。正确性应该首先考虑。 - Pepijn Kramer

显示剩余16条评论

7个回答

4

这里有一个简单的解决方案：

具有明确定义的行为；
适用于所有的int32_t值，包括INT32_MIN和INT32_MAX；
生成无分支代码，可以在这个 Godbolt 比较中验证。

int check_adjacent(int32_t num1, int32_t num2) {
    return 1ULL + num1 - num2 <= 2;
}

- chqrlie

0

尽管我对优化的评论，但我无论如何还是做了，至少是一个子集。要优化代码，您需要包含上下文。在我们这里的情况下，两个参数n32_1和n32_2的统计频率是多少？最优解将首先处理最频繁出现的情况，这使我得出了最佳答案。

我展示了当两个参数都在INT_MIN到INT_MAX范围内随机时的最佳解决方案。考虑到我的迄今为止无瑕疵的记录，这些话可谓勇敢。

我断言首先要做的最好的事情是获取两个参数的差异。然后发现最常见的情况，即它们不属于有趣的空间。这样就得出了很好的答案：

int64_t d = (int64_t)n32_1 - (int64_t)n32_2;
if (d > 1 || d < -1) 
    return 0;
return 1;

现在无论是使用if还是？都更快，我不知道。正如Charlie的解决方案所示，有一种更好的方法可以做到这一点，它不需要考虑输入概率，并且生成的汇编代码要少得多才能完成工作。我会这样写： return (uint64_t)1 + n32_1 - n32_2 <= 2; 令人惊讶的是，当将int32提升为int64而不是提升为uint64时，会生成多么奇怪的汇编代码。

- SpaceCadet

Charlie在上面给出了正确的答案。使用1ULL是关键，它将两个参数提升为64位无符号整数。这就是我在之前尝试中几乎要实现的提升。 - SpaceCadet

1

Charlie在上面给出了正确的答案。使用1ULL是关键，它将两个参数提升为64位无符号整数。这就是我在之前尝试中几乎要达到的提升效果。 - SpaceCadet

0

对于 INT_MIN - INT_MAX、INT_MIN+1 - INT_MIN、1 - 0、0 - 1 等情况，它的行为是正确的。

bool bTrueIfDiffOneOrZero( int32_t n32_1, int32_t n32_2 ) {
    int64_t bIs1or0, d, n1 = n32_1, n2 = n32_2;
    bIs1or0 = (d = n1 - n2) ? ( d == 1 || d == -1 ? 1 : 0) : 1;
    return bIs1or0;
}

还有其他可以做的改变，比如不要使用bIs1or0，只返回表达式。至于比较汇编，这对我来说是一项新技能。它很有趣，但由于未知原因，我得到了预测的溢出，所以我在这一点上认输。我认为像这样优化某个东西是一个错误，所以我不会试图在汇编级别上与其他答案进行比较。谢谢你的评论。

- SpaceCadet

谢谢Eric，我会修复它并相应地进行编辑。 - SpaceCadet

谢谢Eric，我会修复并相应地进行编辑。 - SpaceCadet

这是一个与堆栈溢出设计有关的问题，我已经修复了代码，但Eric的评论仍然存在，这很好，它具有历史准确性，但对其他人来说可能会造成困惑。有人取消了答案的不当扣分，这很酷！我没有更好的答案来解决堆栈溢出设计的问题，总体而言，它还是相当不错的。但这就是为什么我删除了我的其他答案，以发布一个零扣分答案。 - SpaceCadet

这是一个与堆栈溢出设计有关的问题，我修复了代码，但埃里克的评论仍然存在，这没关系，从历史角度来看是准确的，但对其他人来说可能会造成困惑。有人取消了对答案的贬值，这很棒！对于堆栈溢出的设计，我没有更好的答案，总体上它还是相当不错的。但这就是为什么我删除了我的其他答案，以发布一个零贬值的答案。 - SpaceCadet

-1

是的，phuclv的答案是可行的解决方案。它提供了一种更简洁和优化的方法来确定两个int32_t数字之间的差异是否为0或1。通过将num1和num2转换为uint32_t类型，它避免了整数溢出问题，并使用单个比较操作来确定差异是否在所需范围内。这种方法已经得到许多编译器的支持，并且可以有效地进行优化。因此，如果您想进一步优化代码以确定两个数字之间的差异是否为0或1，则可以考虑使用phuclv的代码作为更简洁和高效的选项。

然而，我有一个小问题，关于是否需要(int32_t)转换。由于最终结果需要与-1和1进行比较，我认为可能需要将结果转换回int32_t类型，但我不确定是否正确。

int32_t diff = (int32_t)((uint32_t)num1 - (uint32_t)num2);
bool isZeroOrOne = (diff >= -1 && diff <= 1);

- Air

正如问题中的代码所示，要求测试绝对差是否为1，这意味着有符号差可以是-1、0或+1。此外，该代码具有其他答案的评论中指出的缺陷：在许多情况下会溢出。在典型的C实现中，当num1为INT_MIN且num2为INT_MAX时，它产生1，而结果应该是0。 - Eric Postpischil

@EricPostpischil 它明确地在我的大脑中触发了AI检测器，就像该用户提供的唯一其他答案一样。我承认这是主观的，我会删除我的评论。 - Sven Marnach

@EricPostpischil 您是正确的，我犯了一个严重的错误导致了错误的答案，我很抱歉。我仍然是一个初学者，非常感谢任何纠正。为了不误导其他可能参考我的错误答案的人，我已经更新了我的回答。感谢您的批评和指导。 - Air

1

将其转换为无符号类型可以确保(uint32_t)num1 - (uint32_t)num2不会溢出，但是结果值可能不适合于int32_t，因此将其转换回int32_t并不能提供有效的解决方案。在开始时将其转换为int64_t并将其用于算术和测试即可。如果无法这样做，并且想要将其限制为32位类型，则需要进行额外的测试以避免溢出或实现定义的转换。一旦有了可行的代码，就需要考虑性能问题。该问题要求快速检查。 - Eric Postpischil

-2

这适用于任意两个int32_t类型的n1和n2，包括INT32_MAX、INT32_MIN，不会溢出。返回值bIs1or0。

double d, bIs1or0 = (d = n1 - n2) ? (d == 1 ? 1 : 0) : 1;

- SpaceCadet

3

您已经发布了三个错误答案（并删除了其中两个）。首先，仅显示代码而没有解释的答案通常不是一个好答案。它应该解释代码。这不仅有助于读者理解答案（如果它是正确的），还可以帮助人们解释为什么您走错了方向。从一开始就是错误的n1 - n2。对于某些输入，它会溢出，并将其分配给double也无法解决这个问题，因为在溢出之前不会发生转换为double。 - Eric Postpischil

3

你已经发了三个错误答案（并且迄今为止删除了其中两个）。首先，仅显示代码而没有解释的答案通常不是一个好答案。它应该解释代码。这不仅可以帮助读者理解答案（如果它是正确的），还可以帮助人们解释为什么你走错了方向。n1 - n2从一开始就是错误的。对于某些输入，它会溢出，并且将其分配给double类型也无法修复，因为在溢出之前并不会进行转换为double类型。 - Eric Postpischil

4

当它溢出时，C标准并没有定义其行为。即使它被定义为模2^32的常见行为，这意味着INT32_MIN - INT32_MAX将产生1，这将触发错误的结果1而不是0。您可以通过先转换为double来避免这种情况。然而，涉及到double总体来说对性能来说不是一个好主意；整数和浮点数之间的转换通常不是非常快速的，而这个问题的重点是找到一个快速的解决方案。 - Eric Postpischil

4

当溢出发生时，C标准并未定义其行为。即使它被定义为模2^32的循环包裹，这是一种常见的行为，意味着INT32_MIN - INT32_MAX将产生1，而不是正确的结果0。您可以通过先转换为double来避免这个问题。然而，涉及到double本身对性能来说是一个不好的主意；整数和浮点数之间的转换通常不是非常快速的，而这个问题的重点是找到一个快速的解决方案。 - Eric Postpischil

4

当溢出发生时，C标准并未定义其行为。即使定义为模2^32的循环包裹，这是一种常见的行为，意味着INT32_MIN - INT32_MAX将产生1，而不是正确的结果0。您可以通过先转换为double来避免这种情况。然而，涉及到double本身对性能来说是一个不好的主意；整数和浮点数之间的转换通常不是很快，而这个问题的重点是找到一个快速的解决方案。 - undefined

显示剩余25条评论

-2

你的问题意味着你有两个连续的或者相同的数字。如果其中一个是偶数，另一个必须是奇数才能返回1。看一下这个条件解决方案。

bool res = ((num1%2) && (!(num2%2))) ?
    true : ((!(num1%2)) && (num2%2))) ? true : false;

干杯。

- Iman Abdollahzadeh

如果两个数字之间的差距大于1或0，为什么它会抛出1或0（如您所要求）？ - Iman Abdollahzadeh

我只是尝试回答你的问题，没有更一般性的解释。解释你所写的意思就是我所说的。 - Iman Abdollahzadeh

嗯，这个实现既有条件分支又有模运算。我怀疑它不会比朴素的实现更快（虽然我也怀疑任何人都无法测量任何性能差距）。 - Jeremy Friesner

@JeremyFriesner 一个好的编译器会将%2转换为位掩码操作，所以它并没有看起来那么糟糕。但我仍然不明白这怎么可能是一个正确的解决方案，更快的就更不用说了。 - Mark Ransom

正如Mark Ransom所说，我可以提到位掩码，但这仍然不够易读。我认为这个解决方案比将两个uint32转换为int32的开销要小。@JeremyFriesner - Iman Abdollahzadeh

显示剩余9条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- phuclv · Accepted Answer

编译器已经知道像这样的范围比较的优化技巧，不需要做任何花哨的事情，只需使用它即可。

int32_t diff = uint32_t(num1) - uint32_t(num2);
bool isZeroOrOne = diff >= -1 && diff <= 1;

编译器将优化为单个比较 (uint32_t)(num1 - num2 + 1) <= 2，正如 Raymond Chen 所评论的那样。

强制转换为 unsigned 是必需的，以避免由于整数溢出而导致未定义行为。或者在支持的编译器中使用 -fwrapv。

在Godbolt上的演示。正如您所看到的，编译器将下面的函数编译成完全相同的指令

#include <cstdint>

bool diff1(int32_t num1, int32_t num2)
{
    int32_t diff = uint32_t(num1) - uint32_t(num2);
    return diff >= -1 && diff <= 1;
}

bool diff2(int32_t num1, int32_t num2)
{
    int32_t diff = uint32_t(num1) - uint32_t(num2);
    return (uint32_t)(diff - (-1)) <= (1 - (-1));
}