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.

Which kind of "quick" do you need? Quick to write? Quick to read? Quick to understand? Quick to compile? Quick to execute? Assuming speed of execution, how much quicker does it need to be than the code examples you showed? How fast did you time the shown solutions? — Yunnosch, Sep 22 '20 at 19:29
@Yunnosch: It's about gas-cost, not time. The original question is in Solidity, which carries the same "integer-type nature" as C, and the equivalent of Solidity gas-cost in C is CPU performance (though I can't really go down to the opcode level here, because then it depends on the underlying HW). And the reason I've asked it here in C is because there's a much larger audience for that language, than there is for Solidity (and on a different stack exchange website). Thanks. — goodvibration, Sep 22 '20 at 19:35
@EOF: Thank you, but `abs` embeds the same logical branching presented in each one of the two options that I presented in my question (and of which I was hoping to avoid). — goodvibration, Sep 22 '20 at 19:37
What about near the "boundary" of unsigned numbers? Eg do you consider the difference between UINT_MAX and 0 to be at most 1? (after all, adding 1 to it results in zero). Your original expression doesn't, but maybe that case was not considered — harold, Sep 22 '20 at 19:38
@harold: No, I don't. The difference is arithmetic (not 2s-complement-dependent). The two options in my question assume no overflow in adding. — goodvibration, Sep 22 '20 at 19:38
@goodvibration That code with `abs()` generates much better assembly code on basically all architectures on godbolt than your proposed solutions. I especially like MIPS: `f(int, int): subu $4,$4,$5 addiu $2,$4,1 j $31 sltu $2,$2,3` See the other functions for comparison: https://godbolt.org/z/bc13j7 — EOF, Sep 22 '20 at 19:39
@goodvibration Note there is no 2s-complement concern or issue with `unsigned`. There is overflow, but no 2's complement. — chux - Reinstate Monica, Sep 22 '20 at 20:15
@goodvibration "The difference is arithmetic" seems to address the `0,UINT_MAX` issue as No, these 2 values are not within 1. Yet "assume no overflow in adding." seems to say the `0,UINT_MAX` is a "don't care". For clarity, is `0,UINT_MAX` within 1, not within 1, or you do not care about this case? — chux - Reinstate Monica, Sep 22 '20 at 20:20
@chux-ReinstateMonica: the arithmetic (absolute) difference between 0 and MAX is larger than 1. — goodvibration, Sep 22 '20 at 20:32
@chux-ReinstateMonica: Would you be kind enough to read [this question](https://stackoverflow.com/q/64568541/7400903)? Thank you. — goodvibration, Oct 28 '20 at 09:22

Antti Haapala -- Слава Україні · Answer 1 · 2020-09-22T20:24:08.753

4

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.

edited Sep 22 '20 at 20:24

answered Sep 22 '20 at 19:40

Antti Haapala -- Слава Україні

129,958
22
279
321

Assuming it works, `x - y + 1 <= 2` is brilliant!!! – goodvibration Sep 22 '20 at 20:19
If `x == y` then `x - y + 1 == 1`. If `x == y + 1` then `x - y + 1 == 2`. If `x == y - 1` then `x - y + 1 == 0`. Yup, this is indeed brilliant! – goodvibration Sep 22 '20 at 20:23
And it works if the difference is unsigned; with signed you need to check that the difference is also >= 0 – Antti Haapala -- Слава Україні Sep 22 '20 at 20:25
1

Well, if `x == 0` and `y == MAX`, then `x - y + 1 == 0`, so not perfect. – goodvibration Sep 22 '20 at 20:25
@goodvibration yes, you need to single the `MAX` out anyway, if it is 2 ** 256 - 1 then there might be natural ways to avoid it :D – Antti Haapala -- Слава Україні Sep 22 '20 at 20:26
MAX is 2 ^ 256 - 1 though. – goodvibration Sep 22 '20 at 20:26
your original fails with `x = y = MAX` – Antti Haapala -- Слава Україні Sep 22 '20 at 20:30
Ah yes, I explicitly stated no addition overflows! So it is perfect. Thank you! – goodvibration Sep 22 '20 at 20:30
but `x - y` can wrap-around so you cannot use safe math for that, that's the point of this. – Antti Haapala -- Слава Україні Sep 22 '20 at 20:32
2

Perhaps `-~a - b <= 2` --> `~a + b >= -2u` for one less op. – chux - Reinstate Monica Sep 22 '20 at 20:40
1

@chux-ReinstateMonica nice one – Antti Haapala -- Слава Україні Sep 22 '20 at 20:50
1

@goodvibration note that this trick *does* consider UINT_MAX to be within 1 of zero – harold Sep 22 '20 at 21:05
@harold: Yeah, I wrote this up here. – goodvibration Sep 23 '20 at 05:16

chux - Reinstate Monica · Answer 2 · 2020-09-23T14:25:05.530

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.

score 1 · Answer 3 · answered Sep 25 '20 at 19:38

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

answered Sep 25 '20 at 19:38

Falk Hüffner

4,942
19
25

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

3 Answers3

Linked