Rounding integer division without logical operators

Question

I want a function

int rounded_division(const int a, const int b) { 
    return round(1.0 * a/b); 
}

So we have, for example,

rounded_division(3, 2) // = 2
rounded_division(2, 2) // = 1
rounded_division(1, 2) // = 1
rounded_division(0, 2) // = 0
rounded_division(-1, 2) // = -1
rounded_division(-2, 2) // = -1
rounded_division(-3, -2) // = 2

Or in code, where a and b are 32 bit signed integers:

int rounded_division(const int a, const int b) {
    return ((a < 0) ^ (b < 0)) ? ((a - b / 2) / b) : ((a + b / 2) / b);
}

And here comes the tricky part: How to implement this guy efficiently (not using larger 64 bit values) and without a logical operators such as ?:, &&, ...? Is it possible at all?

The reason why I am wondering of avoiding logical operators, because the processor I have to implement this function for, has no conditional instructions (more about missing conditional instructions on ARM.).

Answer 1

a/b + a%b/(b/2 + b%2) works quite well - not failed in billion+ test cases. It meets all OP's goals: No overflow, no long long, no branching, works over entire range of int when a/b is defined.

No 32-bit dependency. If using C99 or later, no implementation behavior restrictions.

int rounded_division(int a, int b) {
  int q = a / b;
  int r = a % b;
  return q + r/(b/2 + b%2);
}

This works with 2's complement, 1s' complement and sign-magnitude as all operations are math ones.

Answer 2

How about this:

int rounded_division(const int a, const int b) {
    return (a + b/2 + b * ((a^b) >> 31))/b;
}

(a ^ b) >> 31 should evaluate to -1 if a and b have different signs and 0 otherwise, assuming int has 32 bits and the leftmost is the sign bit.

EDIT

As pointed out by @chux in his comments this method is wrong due to integer division. This new version evaluates the same as OP's example, but contains a bit more operations.

int rounded_division(const int a, const int b) {
    return (a + b * (1 + 2 * ((a^b) >> 31)) / 2)/b;
}

This version still however does not take into account the overflow problem.