c++ - 没有逻辑运算符的舍入整数除法

Question

我想要一个函数

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

例如，我们有，

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

或者在代码中，a 和 b 是 32 位有符号整数:

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

棘手的部分来了:如何高效(不使用更大的 64 位值)并且没有逻辑运算符(例如 )来实现这个家伙？: , &&, ...?有可能吗？

我之所以想避免使用逻辑运算符，是因为我必须为其实现此功能的处理器没有条件指令 ( more about missing conditional instructions on ARM.)。

Answer 1

a/b + a%b/(b/2 + b%2) 工作得很好——在十亿以上的测试用例中没有失败。它满足了 OP 的所有目标:没有溢出，没有 long long，没有分支，当定义了 a/b 时，它在 int 的整个范围内工作。

没有 32 位依赖项。如果使用 C99 或更高版本，则没有实现行为限制。

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

这适用于 2 的补码、1 的补码和符号幅度，因为所有运算都是数学运算。