Java：如何执行向负无穷大舍入而不是0的整数除法？

Question

（注意：不同于这个问题，因为提问者从未明确指定向0或负无穷方向舍入）

JLS 15.17.2规定整数除法向零舍入。如果我想要对正因子进行类似于floor()的操作（我不关心负除数的行为），什么是最简单的实现方式，能够在所有输入情况下正确运算？

int ifloor(int n, int d)
{
    /* returns q such that n = d*q + r where 0 <= r < d
     * for all integer n, d where d > 0
     *
     * d = 0 should have the same behavior as `n/d`
     *
     * nice-to-have behaviors for d < 0:
     *   option (a). same as above: 
     *     returns q such that n = d*q + r where 0 <= r < -d
     *   option (b). rounds towards +infinity:
     *     returns q such that n = d*q + r where d < r <= 0
     */
}

long lfloor(long n, long d)
{
    /* same behavior as ifloor, except for long integers */
}

（更新：我希望有一个既适用于int，又适用于long算术的解决方案。）

- Jason S

---

这一定是一个重复的问题，但我找不到它，如果它不是一个重复的问题，那么在 StackOverflow 上 3 年多的时间里它还没有出现，我感到非常惊讶。 - Jason S

在处理余数的 d < 0 条件时，我认为您反转了一些符号。看起来您想要选项 (a) 的情况是 0 <= r < -d，而选项 (b) 的情况是 d < r <= 0。 - Mark Dickinson

没错，谢谢你，我确实是指除数的正值。（而且应该是向上舍入） - Jason S

Answer 1

如果您可以使用第三方库，Guava 有这个功能：IntMath.divide(int, int, RoundingMode.FLOOR) 和 LongMath.divide(int, int, RoundingMode.FLOOR)。(声明：我为Guava做出了贡献。)

如果您不想使用第三方库，仍然可以查看实现方法。

- Louis Wasserman

---

为什么Guava没有包含双精度除法函数？ - voipp

@voipp：你会用它来做什么？它与普通的双精度除法有何不同？ - Louis Wasserman

Answer 2

我针对long做了所有的事情，因为对于int来说答案是相同的，只需将每个long替换为int，并将每个Long替换为Integer。

你可以只 Math.floor一个double类型的除法结果，否则...

原始答案：

return n/d - ( ( n % d != 0 ) && ( (n<0) ^ (d<0) ) ? 1 : 0 );

优化后的答案：

public static long lfloordiv( long n, long d ) {

    long q = n/d;
    if( q*d == n ) return q;
    return q - ((n^d) >>> (Long.SIZE-1));
}

（为完整起见，使用 ROUND_FLOOR 舍入模式的 BigDecimal 也是一种选择。）

（新编辑：现在我只是想看看为了好玩能优化到什么程度。使用 Mark's answer，我目前最好的结果是：）

public static long lfloordiv2( long n, long d ){

    if( d >= 0 ){
        n = -n;
        d = -d;
    }
    long tweak = (n >>> (Long.SIZE-1) ) - 1;
    return (n + tweak) / d + tweak;
}

（使用比上面更便宜的操作，但字节码稍微更长（29 vs. 26）。）

- trutheality

---

请不要向我推荐 Math.floor。如果它对于 int 变量正常工作（我不确定），那么由于精度不足，它将无法处理 long 变量。 - Jason S

我马上就要出门了，但如果我能在周一对其进行抽查以确保正确性，我会点赞的。谢谢，祝你周末愉快。 - Jason S

不错！一个微不足道的混淆优化：用 n^d < 0 替换 (n<0) ^ (d<0)。编译器可能会为您执行此优化，但我怀疑它是否会这样做。 - Ed Staub

注意：在溢出时，n*d可能会产生不正确的结果。 - Jason S

第二个解决方案是错误的。如果 n 是 -3，d 是 2，那个函数会输出 -1（不正确）。 - Louis Wasserman

Answer 3

对于 n < 0 且 d > 0 的情况，有一个相当简洁的公式可用：取 n 的按位补码，进行除法计算，然后再取结果的按位补码。

int ifloordiv(int n, int d)
{
    if (n >= 0)
        return n / d;
    else
        return ~(~n / d);
}

对于余数的计算，类似的结构也适用（与ifloordiv兼容，通常不变式ifloordiv(n, d) * d + ifloormod(n, d) == n得到满足），结果始终在范围[0, d)内。

int ifloormod(int n, int d)
{
    if (n >= 0)
        return n % d;
    else
        return d + ~(~n % d);
}

对于负除数，公式并不那么简洁。以下是ifloordiv和ifloormod的扩展版本，它们遵循您的“好用”选项（b）的行为。

int ifloordiv(int n, int d)
{
    if (d >= 0)
        return n >= 0 ? n / d : ~(~n / d);
    else
        return n <= 0 ? n / d : (n - 1) / d - 1;
}

int ifloormod(int n, int d)
{
    if (d >= 0)
        return n >= 0 ? n % d : d + ~(~n % d);
    else
        return n <= 0 ? n % d : d + 1 + (n - 1) % d;
}

对于 d < 0 的情况，当 d == -1 且 n 是 Integer.MIN_VALUE 时，会出现无法避免的问题，因为这时数学结果会溢出类型。在这种情况下，上述公式返回包装后的结果，就像通常的Java除法一样。据我所知，这是唯一一个我们会默默地得到“错误”结果的角落案例。

- Mark Dickinson

---

@trutheality：天啊，我真是个傻瓜！谢谢，我会立即修复它的！ - Mark Dickinson

@trutheality：没错，除了结果仍然是MIN_VALUE，这在数学上是错误的（但对于2 ** <whatever>取模来说可能足够好）。我有一种不祥的预感，在“d < 0”的情况下还有其他边角案例潜伏着，但我没有花时间去弄清楚它们都是什么。也许我应该这样做。 - Mark Dickinson

哦，原来我不知道除法实际上也可能溢出。 - trutheality

@trutheality：我编辑了最后一段，有没有更好？据我所知，那个情况确实是唯一的特殊情况。 - Mark Dickinson

Answer 4

return BigDecimal.valueOf(n).divide(BigDecimal.valueOf(d), RoundingMode.FLOOR).longValue();

- jtahlborn