如何对负数进行整数除法并*向下*取整？

Question

看起来，每当我将一个负整数除以正整数时，我需要将其向下取整（朝着 -inf），而不是朝着 0。但是 C# 和 C++ 都会朝着 0 取整。

所以我想我需要一个 DivideDownward() 方法。我可以用几行代码编写它，并测试负数等等，但我的想法似乎有些笨拙。所以我在想是否我遗漏了什么，是否您有一种“优雅”的方法来朝负数方向取整。

- Conrad Albrecht

---

给出你想要的行为的示例。 - Matthew Flaschen

例子？好的，我的意思是我想让(-5)/3得出-2，而不是-1。但我认为这个例子对于这个（在我看来）已经很清楚的问题没有任何帮助。 - Conrad Albrecht

Answer 1

您可以通过这样做来消除任何分支：

您可以通过这样做来消除任何分支：

inline int DivideRoundDown(int a_numerator, int a_denominator)
{
    return (a_numerator / a_denominator) + ((a_numerator % a_denominator) >> 31);
}

- ben135

---

这个函数是否有任何假设，还是可以适用于所有正/负操作数的组合？ - cubuspl42

@cubuspl42 依赖于a/b与a%b具有相同的符号 - 不确定是否由标准保证，但我认为所有现代编译器/硬件都是如此 - 还依赖于有符号右移是算术的（如果我记得正确的话，即使是今天 - 是的，我知道我晚了十多年，但可能还有其他晚读者... - 尽管所有我知道的编译器/硬件都是算术右移） - 最后依赖于int具有32位，这绝对不是每台机器的情况（有较小int的MCU）。 - undefined

（通过 >> sizeof(int) * CHAR_BIT - 1 可以轻松满足最后一个要求。） - undefined

Answer 2

每当我将一个负整数除以一个正整数时，需要它向下取整。这真是太糟糕了。Knuth写过为什么这样做是正确的方式，但我们现在却被遗留下来的整数硬件所束缚。

如果您能够承受精度损失，最简单和最干净的方法是将32位整数转换为64位的double，并在将商转换回整数时使用FP舍入模式向负无穷方向舍入。今天的浮点运算单元非常快，实际上可能比整数单元更快地进行除法运算；要确保，您需要进行测量。

如果需要完整的64位整数精度，我作为编译器编写者处理这个问题是通过进行两个条件分支来实现，这样您就可以除以magnitudes，然后得到正确的符号。但是当时条件分支与除法相比较便宜，但随着硬件的发展，在今天的硬件上进行实验之前，我必须先进行实验才能推荐某些东西。

原则上，您可以通过使用传统的英特尔80位浮点数字对64位整数进行浮点技巧，但这是极其不可移植的，而且我不相信英特尔会继续使该单位快速。这些天，浮点速度在SSE单元中。

寻找其他技巧的地方包括汉克沃伦（Hank Warren）的书Hacker's Delight（我的副本在工作中）和标准ML的MLton编译器，它要求整数除法向负无穷方向舍入。

无论你做什么，当你确定使用C++或C99时，请将你的除法例程放入.h文件中，并使其成为static inline. 这样，当你的解决方案在5年内交付新的高科技硬件时被证明不够优秀时，你只需更改一个地方。

- Norman Ramsey

---

我曾认为int32 -> double不会失去任何精度。但是我刚刚优化了一些浮点代码，其中fstp操作（在接近0的数字上）占用了大部分CPU时间。也许与此无关，但现在我对不必要的浮点数有些失望。;) - Conrad Albrecht

Answer 3

假设b始终为正数，则以下是一种简单的解决方案：

inline int roundDownDivide(int a, int b) {
  if (a >= 0) return a/b; 
  else return (a-b+1)/b;
}

- Dr.Altan

---

roundDownDivide(-2147483648, 2) == 1073741823 -- 如果 a < INT_MIN + b - 1，则会溢出，同时不是最快的。请参见我的答案进行详细评估。 - Yakov Galka

Answer 4

如果您希望用相对简洁的方式只使用整数来编写此代码，则可以这样编写：

var res = a / b - (a % b < 0 ? 1 : 0);

这可能编译成许多指令，但与使用浮点数相比，它可能仍然更快。

- Tomas Petricek

---

@Tom，说得好。我是在考虑a为负数的情况。所以我想一个通用版本应该是：a / b - (a < 0 && a % b != 0 ? 1 : 0)。 - Matthew Flaschen

我认为所给答案取决于具体实现，但Matthew的修改看起来简洁可靠。如果这是一个答案，我会打勾的。谢谢（大家）！ - Conrad Albrecht

@Matthew：实际上，这在C89和C99中都是保证可行的——除非b==0，否则它们要求(a/b)*b+a%b==a，即使/和%返回的实际值对于负操作数是实现定义的。如果内置的/向-无穷大舍入而不是向0舍入，则您的版本将失败。 - Chris Dodd

如果 b 为负数，这将产生错误的结果。例如，-1 / -2 计算出的结果是 -1 而不是 0。 - Mr. Smith

@Mr.Smith：我发布了一个适用于负数b的版本。 - Yakov Galka

Answer 5

许多编程语言，包括较旧的标准C和C ++，保证除法规则，即：

a = b * (a / b) + a % b

即使 a/b 和 a%b 的确切值未定义^[0]，这也可以被利用在许多语言和平台上计算所需的结果，使用以下（等效的）代码：

int divF(int a, int b) { return a / b - (a % b < 0); }

这是@TomasPetricek回答中的版本。但是，它只适用于>0！

以下代码适用于任何不等于0的b：^[1]

int sign(int x) { return (x > 0) - (x < 0); }
int divF2(int a, int b) { return a / b - (sign(a % b) == -sign(b)); }

然而，向下取整除法（也称作flooring division或Knuth's division）并不总是可取的。有人认为欧几里得除法是最常用的一种，当b>0时向下取整，当b<0时向上取整。它具有这样一个好的特性：适配定义的余数的值对于所有的a和b都是非负的，与它们的符号无关。此外，对于二次补码机器上的2的幂除数，它与位移和掩码重合。是的，它也更快速计算。

int divE(int a, int b) {
    int c = a % b < 0;
    return a / b + (b < 0 ? c : -c);
}

所有三个版本都可以在amd64上使用clang -O3生成无分支代码。然而，在二进制补码架构上，以下内容可能会稍微快一些：

int divE2(int a, int b) { return a / b + (-(a % b < 0) & (b < 0 ? 1 : -1)); }

生成的代码

divF:
    cdq
    idiv    esi
    sar edx, 31
    add eax, edx

divF2:
    cdq
    idiv    esi
    xor ecx, ecx
    test    edx, edx
    setg    cl
    sar edx, 31
    add edx, ecx
    xor ecx, ecx
    test    esi, esi
    setg    cl
    shr esi, 31
    sub esi, ecx
    xor ecx, ecx
    cmp edx, esi
    sete    cl
    sub eax, ecx

Chazz:
    cdq
    idiv    esi
    test    edx, edx
    cmove   edi, esi
    xor edi, esi
    sar edi, 31
    add eax, edi

divE:
    cdq
    idiv    esi
    mov ecx, edx
    shr ecx, 31
    sar edx, 31
    test    esi, esi
    cmovs   edx, ecx
    add eax, edx

divE2:
    cdq
    idiv    esi
    sar edx, 31
    shr esi, 31
    lea ecx, [rsi + rsi]
    add ecx, -1
    and ecx, edx
    add eax, ecx

基准测试

simple truncating division:
    2464805950:  1.90 ns -- base

euclidean division:
    2464831322:  2.13 ns -- divE
    2464831322:  2.13 ns -- divE2

round to -inf for all b:
    1965111352:  2.58 ns -- Chazz
    1965111352:  2.64 ns -- divF2
    1965111352:  5.02 ns -- Warty

round to -inf for b > 0, broken for b < 0:
    1965143330:  2.13 ns -- ben135
    1965143330:  2.13 ns -- divF
    1965143330:  2.13 ns -- Tomas
    4112595000:  5.79 ns -- runevision

round to -inf, broken for b < 0 or some edge-cases:
    4112315315:  2.24 ns -- DrAltan
    1965115133:  2.45 ns -- Cam
    1965111351:  7.76 ns -- LegsDrivenCat

使用clang -O3 编译，在FreeBSD 12.2上运行，i7-8700K CPU @ 3.70GHz。第一列是生成相同结果的校验和分组算法。base 是用于测量测试开销的最简单的截断除法。

测试平台：

static const int N = 1000000000;
int rng[N][2], nrng;
void push(int a, int b) { rng[nrng][0] = a, rng[nrng][1] = b, ++nrng; }
SN_NOINLINE void test_case(int (*func)(), const char *name) {
    struct timespec t0, t1;
    clock_gettime(CLOCK_PROF, &t0);
    int sum = func();
    clock_gettime(CLOCK_PROF, &t1);
    double elapsed = (t1.tv_sec - t0.tv_sec)*1.e9 + (t1.tv_nsec - t0.tv_nsec);
    printf("%10u: %5.2f ns -- %s\n", sum, elapsed/N, name);
}

#define ALL_TESTS(X) X(base) X(divF) X(divF2) X(divE) X(divE2) X(ben135) X(DrAltan) X(Cam) X(Tomas) X(Warty) X(Chazz) X(runevision) X(LegsDrivenCat)

#define LOOP_TEST(X) \
    SN_NOINLINE int loop_##X() { \
        int sum = 0; \
        for(int i = 0; i < N; ++i) sum += X(rng[i][0], rng[i][1]); \
        return sum; \
    } \
/**/
ALL_TESTS(LOOP_TEST)

int main() {
    srandom(6283185);
    push(INT_MAX, 1); push(INT_MAX, -1); push(INT_MIN, 1);
    push(INT_MAX, 2); push(INT_MAX, -2); push(INT_MIN, 2); push(INT_MIN, -2);
    while(nrng < N) {
        int a = random() - 0x40000000, b;
        do b = (random() >> 16) - 0x4000; while(b == 0);
        push(a,b);
    }

#define CALL_TEST(X) test_case(loop_##X, #X);
    ALL_TESTS(CALL_TEST)
}

脚注/参考文献

0. 现在在C和C++中定义为截断舍入。因此，负数向上舍入，正数向下舍入。这就是硬件除法器所做的。这是一个不好的选择，因为这是最不实用的舍入规则。
1. Daan Leijen. 计算机科学家的除法和模运算。2001年12月。
2. Raymond T. Boute. 函数div和mod的欧几里得定义。1992年4月。

- Yakov Galka

Answer 6

注意：此文章针对a=-1的输入结果不正确，请参考其他答案。

---

[c++]

这可能就是你所说的“笨拙”，但这是我想出来的方法。

int divideDown(int a, int b){
    int r=a/b;
    if (r<0 && r*b!=a)
        return r-1;
    return r;
}

在if语句中，我使用了 r<0 - 但我不确定这是否是你想要的。你可能希望将if语句改为：

if (a<0 && b>0)

这与您所描述的“似乎每当我将一个负整数除以正整数”是一致的。

- Cam

---

这就是我所说的 klugey，但我不知道有什么更好的方法。特别是对于 r*b!=a 测试，它可能比 a%b!=0 更有效，并且证明了与提供的单行表达式相比额外代码行的合理性，我认为这是“答案”。 - Conrad Albrecht

我不确定，但是应该是 if (r<=0 && r*b!=a) 吧？ - Chris Burt-Brown

更糟糕的是，按照这种方式编写的代码，在a=-1时会产生错误的答案，如果将其改为r<=0，则在a=1时会产生错误的答案。这个答案不应该被接受，因为它会产生不正确的结果。 - Joe Strout

无法删除，因为它是被接受的答案。我们将尝试通过一个解决方案来解决，并在此之前已编辑并标注警告。感谢您发现了这个漏洞！ - Cam

@Cam 我原以为即使答案已被采纳，也可以删除自己的答案。事实上，我认为这样做会获得某种自我批评徽章。也许并不是这样。 - csj

Answer 7

这是一个在除数为负数时也能工作的版本：

int floor_div2(int a, int b)
{
  int rem = a % b;
  int div = a/b;
  if (!rem)
    a = b;
  int sub = a ^ b;
  sub >>= 31;
  return div+sub;
}

- Chazz

---

这是在此页面上最快的解决方案，根据我的基准测试，它可以为所有边缘情况提供正确的结果。我给予巨大的赞同。 - Yakov Galka

@YakovGalka“对于所有边缘情况都给出正确的结果。”floor_div2(INT_MIN，-1)在a/b方面会导致问题。当int的大小不是32位时会失败。它依赖于二进制补码——这通常是这些天的情况。 - chux - Reinstate Monica

@chux-ReinstateMonica，对于INT_MIN/-1它实际上做了正确的事情。让我们不要挑剔硬编码的31 - 任何人都可以修复它，而且算法不依赖于int的大小。至于二进制补码 - 它现在是无处不在的。 - Yakov Galka

@YakovGalka 在 C/C++ 中，INT_MIN/-1 是_未定义行为_。它能在你的情况下正常工作并不代表语言规定它对所有情况都有效。 - chux - Reinstate Monica

@chux-ReinstateMonica 我知道这是什么意思；我的观点是，在这种情况下，floor_div2的行为与内置除法相同，这正是我期望这样一个函数所做的。 - Yakov Galka

Answer 8

对于2的幂次方，根据编译器实现（Visual Studio），您可以使用右移操作。

-5 >> 2 == -2

- Michel de Ruiter

Answer 9

Math.Floor((double)a/(double)b)
如果你需要它作为int类型，在此之后进行转换
(int)Math.Floor((double)a/(double)b)

- Warty

---

decimal是最慢的数值类型（参见http://msdn.microsoft.com/en-us/library/xtba3z33.aspx），在这里并没有什么用处。使用`float`或`double`会更加合适。 - Matthew Flaschen

你也不需要转换分母，只需要转换分子。 - user315772

@Matthew Flaschen：我正在考虑这个问题。我没有意识到他所说的int是int32。如果为a和b插入无关的值[Int64.MaxValue-1和Int64.MaxValue]，使用double会因为浮点误差而出现错误，你会得到1而不是0。答案已经修正。 - Warty

这个答案是可行的，但考虑到浮点运算的性能成本，我认为它并没有比我的“笨拙”方法更好。 - Conrad Albrecht

Answer 10

阿特兰博士的解决方案是最常见的答案，但如果您知道a不会小于某个固定数字，则可以添加最小的b的倍数以使其为正值，然后调整结果。例如，如果a始终大于等于-10 * b，则可以说：

return (a + 10 * b) / b - 10

或者，如果您只想在 a 为正数或0时获得正确的结果，并在 a 为负数时获得一些负结果（例如，用于测试结果是否>= 0，而不包括范围 a = [-1; -b +1]），您可以执行以下操作

return (a + b) / b - 1;

对于 [-1，-b+1] 和 [-b；-2*b+1]，该函数将返回-1。但是，如果您只是想确定除法的结果是否为正，则这并不重要。实际上，我们只是更改四舍五入方式，使其向 -1 而不是 0 的方向取整。

- hoegsberg