Check if the difference between two unsigned integers is at most 1

Question

I'm looking for a quick way to check whether or not the difference between two unsigned integers is at most 1.

Obviously, I can do it directly via x <= y + 1 && y <= x + 1.

Another way is via x == (x + y) / 2 || y == (x + y) / 2.

But I've figured there must be a bit-wise trick to achieve that.

So I would be happy to hear suggestions.

You may assume that the two input types are identical, and that there is no overflow in adding them.

Answer 1

A relatively simple expression that is correct for all inputs is

(x - y + (y > x)) <= 1

(assuming that > yields 0 or 1, as in C).

Answer 2

I'm looking for a quick way to check whether or not the difference between two unsigned integers is at most 1.

Often a quick way ends up with a solution that works most of the time but not all - thus leaving a bug for some future coder to solve.

That is the case here with various proposed solutions.

A good alternative it to form a test harness to 1) test for correctness 2) allow profiling to assess performance.

A good approach is to let the compile optimize a certainly correct solution like ref() or methodC().

---

Below is a functional test harness.

#include <assert.h>
#include <limits.h>
#include <stdio.h>

int ref(unsigned int a, unsigned int b) {
  assert(UINT_MAX <= LLONG_MAX);
  long long al = a;
  long long bl = b;
  long long diff = al - bl;
  return diff >= -1 && diff <= 1;
}

int method1(unsigned int a, unsigned int b) {
  return a - b + 1 <= 2;
}

int method2(unsigned int a, unsigned int b) {
  return -~a - b <= 2;
}

int method3(unsigned int a, unsigned int b) {
  return ~a + b >= -2u;
}

int method_OP1(unsigned int x, unsigned int y) {
  return x <= y + 1 && y <= x + 1;
}

int method_OP2(unsigned int x, unsigned int y) {
  return x == (x + y) / 2 || y == (x + y) / 2;
}

int methodC(unsigned int a, unsigned int b) {
  return a < b ? ((b - a) <= 1) : ((a - b) <= 1);
}

typedef int (*fun)(unsigned int, unsigned int);

int test1(const char *s, fun f, unsigned int a, unsigned int b) {
  int y1 = ref(a, b);
  int y2 = f(a, b);
  if (y1 != y2) {
    printf("%-10s %10u and %10u: ", s, a, b);
    printf("ref %d ", y1);
    printf("method %d\n", y2);
  }
  return y1 != y2;
}

int main(void) {
  fun f[] = {method1, method2, method3, method_OP1, method_OP2, methodC};
  char *s[] = {"method1", "method2", "method3", "method_OP1", "method_OP2",
      "methodC"};
  int fn = sizeof f / sizeof f[0];
  unsigned u[] = {0, 1, 2, 3, //
      UINT_MAX - 3, UINT_MAX - 2, UINT_MAX - 1, UINT_MAX};
  int n = sizeof u / sizeof u[0];
  for (int fi = 0; fi < fn; fi++) {
    for (int ia = 0; ia < n; ia++) {
      for (int ib = 0; ib < n; ib++) {
        if (test1(s[fi], f[fi], u[ia], u[ib]) && 0) {
          ia = n;
          break;
        }
      }
    }
  }
}

Output failures

method1             0 and 4294967295: ref 0 method 1
method1    4294967295 and          0: ref 0 method 1
method2             0 and 4294967295: ref 0 method 1
method2    4294967295 and          0: ref 0 method 1
method3             0 and          1: ref 1 method 0
method3             0 and 4294967295: ref 0 method 1
method3             1 and          2: ref 1 method 0
method3             2 and          3: ref 1 method 0
method3    4294967292 and 4294967293: ref 1 method 0
method3    4294967293 and 4294967294: ref 1 method 0
method3    4294967294 and 4294967295: ref 1 method 0
method_OP1 4294967294 and 4294967295: ref 1 method 0
method_OP1 4294967295 and 4294967294: ref 1 method 0
method_OP1 4294967295 and 4294967295: ref 1 method 0
method_OP2 4294967292 and 4294967292: ref 1 method 0
method_OP2 4294967292 and 4294967293: ref 1 method 0
method_OP2 4294967293 and 4294967292: ref 1 method 0
method_OP2 4294967293 and 4294967293: ref 1 method 0
method_OP2 4294967293 and 4294967294: ref 1 method 0
method_OP2 4294967294 and 4294967293: ref 1 method 0
method_OP2 4294967294 and 4294967294: ref 1 method 0
method_OP2 4294967294 and 4294967295: ref 1 method 0
method_OP2 4294967295 and 4294967294: ref 1 method 0
method_OP2 4294967295 and 4294967295: ref 1 method 0

---

If we use "You may assume that the two input types are identical, and that there is no overflow in adding them." then method_OP2() failures can be forgiven. This assumption does not directly cover failures of other approaches.

Answer 3

Since wraparound works, how about just x - y + 1 <= 2. And since -n - 1 is one's complement, i.e ~, and Solidity integers have wraparound just like C unsigned integers, then you could also use -~x - y <= 2 which has one constant less.

#include <stdio.h>

void test(unsigned int a, unsigned int b) {
    printf("%d and %d: ", a, b);
    printf("method1 %d ", a - b + 1 <= 2);
    printf("method2 %d\n", -~a - b <= 2);
}

int main(void) {
    test(1, 1);
    test(1, 2);
    test(1, 3);
    test(1, 4);
    test(2, 1);
    test(3, 1);
    test(4, 1);
}

Output:

1 and 1: method1 1 method2 1
1 and 2: method1 1 method2 1
1 and 3: method1 0 method2 0
1 and 4: method1 0 method2 0
2 and 1: method1 1 method2 1
3 and 1: method1 0 method2 0
4 and 1: method1 0 method2 0

---

In Solidity, bit twiddling does not really help you that much - you need to look into the gas cost table for different operations. The first does 3 verylow arithmetic operations and two pushes, the second one does 4 verylow arithmetic operations and one push, so they should be more or less comparable.