fast check if the difference between two int32_t is 1 or 0

Question

A straight forward way would be

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

or to simply check for all possible cases:

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

Is there a more optimized way?

Answer 1

Compilers already knows optimization techniques for range comparison like this, no need to do anything fancy and just use this

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

The compiler will optimize into a single comparison (uint32_t)(num1 - num2 + 1) <= 2 as Raymond Chen commented

The cast to unsigned is required to avoid undefined behavior due to integer overflow. Or use -fwrapv in supported compilers

Demo on Godbolt. As you can see compilers compile the below function into exactly the same instructions

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

Answer 2

Here is a simple solution that

• has defined behavior;
• works for all int32_t values including INT32_MIN and INT32_MAX;
• generates branchless code, as can be verified on this Godbolt comparison.

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

Answer 3

this behaves correctly for INT_MIN - INT_MAX, INT_MIN+1 - INT_MIN, 1 - 0, 0 - 1 etc.

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

there are other changes that can be done like not having the bIs1or0, just return the expression. as far as comparing assembly that is a new skill for me. it is interesting, and now for unknown reasons i am getting the predicted overflow, so i concede on that point. i am in the camp that its a mistake to try and optimize something like this so i will not attempt to compare the above answer with the others at the assembler level. thanks for your comments.

Answer 4

in spite of my comments about optimization i did it anyway, at least a subset. to optimize code you need to include the context. in our case here, what are the statistical frequencies of the two arguments n32_1 and n32_2? the optimal solution will deal with the most frequent case first, which has led me to the optimal answer.

i am showing the optimal solution for the case where both arguments are random in the range INT_MIN through INT_MAX inclusive. brave words considering how flawless my track record is to date.

i assert the best thing to do first is to take the difference of the two arguments. then discover the most common case, which is they do NOT fall in the interesting space. that leads to the answer quite nicely:

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

now whether using if or ? is faster i do not know. as chqrlie's solution shows, there is a better way to do this that doesn't have to consider anything about the input probabilities and produces much less assembler code to get the job done. i would write it this way return (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

Your question means you have either two successive or two identical numbers. If one is even, the other has to be odd to fulfil returning 1. Have a look at this conditional solution.

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

Cheers.

Answer 6

This works for any two int32_t n1 and n2 including INT32_MAX, INT32_MIN, no overflow. the return value is bIs1or0.

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