不带逻辑运算符的舍入整数除法

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位值），并且不使用诸如之类的逻辑运算符 ，<代码>

我想避免逻辑运算符的原因是，因为我必须为其实现此功能的处理器没有条件指令（更多关于ARM上缺少条件指令的信息）。




Answer 1

怎么样

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

没有溢出：

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

Answer 2

这个怎么样？

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

<代码>（a^b）

编辑

正如@chux在他的评论中指出的，由于整数除法，这个方法是错误的。这个新版本的评估与OP的示例相同，但包含更多的操作。

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

然而，这个版本仍然没有考虑溢出问题。

Answer 3

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的补码和符号大小，因为所有操作都是数学运算。