Threshold an absolute value

Question

I have the following function:

char f1( int a, unsigned b ) { return abs(a) <= b; }

For execution speed, I want to rewrite it as follows:

char f2( int a, unsigned b ) { return (unsigned)(a+b) <= 2*b; } // redundant cast

Or alternatively with this signature that could have subtle implications even for non-negative b:

char f3( int a, int b )      { return (unsigned)(a+b) <= 2*b; }

Both of these alternatives work under a simple test on one platform, but I need it to portable. Assuming non-negative b and no risk of overflow, is this a valid optimization for typical hardware and C compilers? Is it also valid for C++?

---

Note: As C++ on gcc 4.8 x86_64 with -O3, f1() uses 6 machine instructions and f2() uses 4. The instructions for f3() are identical to those for f2(). Also of interest: if b is given as a literal, both functions compile to 3 instructions that directly map to the operations specified in f2().

Answer 1

Starting with the original code with signature

char f2( int a, unsigned b );

this contains the expression

a + b

Since one of these operands has a signed and the other an (corresponding) unsigned integer type (thus they have the same "integer conversion rank"), then - following the "Usual arithmetic conversions" (§ 6.3.1.8) - the operand with signed integer type is converted to the unsigned type of the other operand.

Conversion to an unsigned integer type is well defined, even if the value in question cannot be represented by the new type:

[..] if the new type is unsigned, the value is converted by repeatedly adding or subtracting one more than the maximum value that can be represented in the new type until the value is in the range of the new type. 60

§ 6.3.1.3/2

Footnote 60 just says that the described arithmetic works with the mathematical value, not the typed one.

Now, with the updated code

char f2_updated( int a, int b ); // called f3 in the question

things would look different. But since b is assumed to be non-negative, and assuming that INT_MAX <= UINT_MAX you can convert b to an unsigned without fearing it to have a different mathematical value afterwards. Thus you could write

char f2_updated( int a, int b ) {
  return f2(a, (unsigned)b); // cast unnecessary but to make it clear
}

Looking again at f2 the expression 2*b further limits the allowed range of b to be not larger than UINT_MAX/2 (otherwise the mathematical result would be wrong). So as long as you stay within these bounds, every thing is fine.

Note: Unsigned types do not overflow, they "wrap" according to modular arithmetic.

Quotes from N1570 (a C11 working draft)

---

A final remark:

IMO the only really reasonable choice to write this function is as

#include <stdbool.h>
#include <assert.h>
bool abs_bounded(int value, unsigned bound) {
  assert(bound <= (UINT_MAX / 2));
  /* NOTE: Casting to unsigned makes the implicit conversion that
           otherwise would happen explicit. */
  return ((unsigned)value + bound) <= (2 * bound);
}

Using a signed type for the bound does not make much sense, because the absolute of a value cannot be less than a negative number. abs_bounded(value, something_negative) would be always false. If there's the possibility of a negative bound, then I'd catch this outside of this function (otherwise it does "too much"), like:

int some_bound;
// ...
if ((some_bound >= 0) && abs_bounded(my_value, some_bound)) {
  // yeeeha
}

Answer 2

As OP wants fast and portable code (and b is positive), it first makes sense to code safely:

// return abs(a) <= b;
inline bool f1_safe(int a, unsigned b ) { 
  return (a >= 0 && a <= b) || (a < 0 && 0u - a <= b);
}

This works for all a,b (assuming UINT_MAX > INT_MAX). Next, compare alternatives using an optimized compile (let the compiler do what it does best).

---

The following slight variation on OP's code will work in C/C++ but risks portability issues unless "Assuming non-negative b and no risk of overflow" can be certain on all target machines.

bool f2(int a, unsigned b) { return a+b <= b*2; }

In the end, OP goal of fast and portable code may find code the works optimally for the select platform, but not with others - such is micro-optimization.