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

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 的补码和 sign-magnitude，因为所有运算都是数学运算。

Answer 2

这个怎么样：

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

如果 a 和 b 有不同的符号，

(a ^ b) >> 31 应该计算为 -1，否则 0，假设 int 有 32 位最左边是符号位。

编辑

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

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

这个版本还是没有考虑溢出问题

Answer 3

那

呢

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

没有溢出：

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

Answer 4

这是您可以使用的粗略方法。如果操作 a*b < 0，则使用遮罩来应用某些东西。

请注意，我没有对此进行适当的测试。

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
}

Answer 5

以下 rounded_division_test1() 满足 OP 的无分支要求 - 如果将 sign(int a)、nabs(int a) 和 cmp_le(int a, int b) 计为 non-branching。有关如何在没有比较运算符的情况下执行 sign() 的想法，请参阅 here。这些辅助函数可以在没有显式调用的情况下集成到 rounded_division_test1()。

该代码演示了正确的功能，可用于测试各种答案。当定义了 a/b 时，这个答案不会溢出。

#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;
}

Answer 6

因为函数似乎是对称的sign(a/b)*floor(abs(a/b)+0.5)

Answer 7

让我贡献一下：

关于：

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

没有分支，没有逻辑运算符，只有数学运算符。但如果 b 大于 INT_MAX/2 或小于 INT_MIN/2.

，它可能会失败

但是如果允许64位计算32位轮。不会失败

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

Answer 8

我想出的用于 ARM M0 的代码（无浮点数，除法速度慢）。它只使用一个除法指令并且没有条件，但如果分子 + (denominator/2) > INT_MAX.

会溢出

ARM M0 上的循环计数 = 7 个循环 + 除法（M0 没有除法指令，因此它依赖于工具链）。

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;
}

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

Rounding integer division without logical operators

c

c++

rounding