快速检查两个int32_t之间的差异是1还是0

Question

一个直接的方法是

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);

有没有更优化的方法？

Answer 1

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

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

它适用于OP方法

abs(num1 - num2)

适用的所有情况。对于

{ INT32_MAX, INT32_MIN }

的边缘情况，两种解决方案都失败了，因为

abs(num1 - num2)

调用未定义的行为，并且如果启用了包装行为

-fwrapv

那么

abs

也会返回 1。如果您知道这些值永远不可能是该对，那么这就是最简单的方法

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));
}

---

如果您想让它适用于所有情况，那么这里有一个解决方案

bool diff(int32_t a, int32_t b)
{
    int32_t am = std::max(a, b);
    int32_t bm = std::min(a, b);
    uint32_t diff = uint32_t(am) - uint32_t(bm);
    return diff <= 1;
}

Godbolt 上的演示和测试

Answer 2

这是一个简单的解决方案

• 有明确的行为；
• 适用于所有

  int32_t

  值，包括

  INT32_MIN

  和

  INT32_MAX

  ；
• 生成无分支代码，可以在此 Godbolt 比较上进行验证。

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

Answer 3

对于 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，只需返回表达式即可。 就比较组装而言，这对我来说是一项新技能。 这很有趣，现在由于未知的原因我得到了预测的溢出，所以我承认这一点。 我认为尝试和优化这样的东西是错误的，所以我不会尝试将上述答案与汇编器级别的其他答案进行比较。 感谢您的评论。

Answer 4

尽管我对优化发表了评论，但我还是做了，至少是一部分。 要优化代码，您需要包含上下文。 在我们的例子中，两个参数 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 或 ?更快我不知道。 正如 chqrlie 的解决方案所示，有一种更好的方法可以做到这一点，无需考虑任何有关输入概率的信息，并且可以生成更少的汇编代码来完成工作。 我会这样写 返回 (uint64_t)1 + n32_1 - n32_2 <= 2; it is amazing how much strange assembler code is generated when you promote the int32 to int64 instead of promoting it to uint64.

Answer 5

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

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

干杯。

Answer 6

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

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