CODEWITHSUNDEEP
c++crounding
Michael Dorner
Michael Dorner

Reputation: 20125

Rounding integer division without logical operators

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

Upvotes: 4

Views: 974

Answers (8)

Craig
Craig

Reputation: 76

Code that I came up with for use on ARM M0 (no floating point, slow divide). It only uses one divide instruction and no conditionals, but will overflow if numerator + (denominator/2) > INT_MAX.

Cycle count on ARM M0 = 7 cycles + the divide (M0 has no divide instruction, so it is toolchain dependant).

int32_t Int32_SignOf(int32_t val)
{
    return (+1 | (val >> 31)); // if v < 0 then -1, else +1
}

uint32_t Int32_Abs(int32_t val)
{
    int32_t tmp = val ^ (val >> 31);
    return (tmp - (val >> 31));

    // the following code looks like it should be faster, using subexpression elimination
    // except on arm a bitshift is free when performed with another operation,
    // so it would actually end up being slower
    // tmp = val >> 31;
    // dst = val ^ (tmp);
    // dst -= tmp;
    // return dst;
}

int32_t Int32_DivRound(int32_t numerator, int32_t denominator)
{
    // use the absolute (unsigned) demominator in the fudge value
    // as the divide by 2 then becomes a bitshift
    int32_t  sign_num  = Int32_SignOf(numerator);
    uint32_t abs_denom = Int32_Abs(denominator);
    return (numerator + sign_num * ((int32_t)(abs_denom / 2u))) / denominator;
}

Upvotes: 1

chux
chux

Reputation: 153303

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.

Upvotes: 9

Amadeus
Amadeus

Reputation: 10655

Let me give my contribution:

What about: 

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

No branch, no logical operators, only mathematical operators. But it could fail if b is great than INT_MAX/2 or less than INT_MIN/2.

But if 64 bits are allowed to compute 32 bits rounds. It will not fail

int rounded_division(const int a, const int b) {
    return a/b + (2LL*(a%b))/b;
}

Upvotes: 1

gmoshkin
gmoshkin

Reputation: 1135

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.

Upvotes: 3

chux
chux

Reputation: 153303

The following rounded_division_test1() meets OP's requirement of no branching - if one counts sign(int a), nabs(int a), and cmp_le(int a, int b) as non-branching. See here for ideas of how to do sign() without compare operators. These helper functions could be rolled into rounded_division_test1() without explicit calls.

The code demonstrates the correct functionality and is useful for testing various answers. When a/b is defined, this answer does not overflow. 

#include <limits.h>
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <errno.h>

int nabs(int a) {
  return (a < 0) * a - (a >= 0) * a;
}

int sign(int a) {
  return (a > 0) - (a < 0);
}

int cmp_le(int a, int b) {
  return (a <= b);
}

int rounded_division_test1(int a, int b) {
  int q = a / b;
  int r = a % b;
  int flag = cmp_le(nabs(r), (nabs(b) / 2 + nabs(b % 2)));
  return q + flag * sign(b) * sign(r);
}

// Alternative that uses long long
int rounded_division_test1LL(int a, int b) {
  int c = (a^b)>>31;
  return (a + (c*2 + 1)*1LL*b/2)/b;
}

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

int test(int a, int b) {
  int q0 = rounded_division(a, b);
  //int q1 = function(a,b);
  int q1 = rounded_division_test1(a, b);
  if (q0 != q1) {
    printf("%d %d --> %d %d\n", a, b, q0, q1);
    fflush(stdout);
  }
  return q0 != q1;
}

void tests(void) {
  int err = 0;
  int const a[] = { INT_MIN, INT_MIN + 1, INT_MIN + 1, -3, -2, -1, 0, 1, 2, 3,
      INT_MAX - 1, INT_MAX };
  for (unsigned i = 0; i < sizeof a / sizeof a[0]; i++) {
    for (unsigned j = 0; j < sizeof a / sizeof a[0]; j++) {
      if (a[j] == 0) continue;
      if (a[i] == INT_MIN && a[j] == -1) continue;
      err += test(a[i], a[j]);
    }
  }
  printf("Err %d\n", err);
}

int main(void) {
  tests();
  return 0;
}

Upvotes: 1

user2889887
user2889887

Reputation: 26

since the function seems to be symmetric how about sign(a/b)*floor(abs(a/b)+0.5)

Upvotes: 0

MSR
MSR

Reputation: 11

This is a rough approach that you may use. Using a mask to apply something if the operation a*b < 0.

Please note that I did not test this appropriately.

int function(int a, int b){
    int tmp = float(a)/b + 0.5;
    int mask = (a*b) >> 31; // shift sign bit to set rest of the bits

    return tmp - (1 & mask);//minus one if a*b was < 0
}

Upvotes: 1

alk
alk

Reputation: 70883

What about 

  ...
  return ((a + (a*b)/abs(a*b) * b / 2) / b);
}

Without overflow:

  ...
  return ((a + ((a/abs(a))*(b/abs(b))) * b / 2) / b);    
}

Upvotes: 1

Related Questions