Java:如何执行向-Infinity而不是0舍入的整数除法?

注意 :与其他问题不同,因为OP从未明确指定向0或-Infinity舍入)

JLS 15.17.2说整数除法向零舍入 。 如果我想要积极除数的类似floor()的行为(我不关心负除数的行为),那么实现这一点的最简单方法是在数值上对所有输入都是正确的吗?

 int ifloor(int n, int d) { /* returns q such that n = d*q + r where 0 <= r  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 */ } 

(更新:我想为intlong算法提供解决方案。)

如果你可以使用第三方库, Guava就有: IntMath.divide(int, int, RoundingMode.FLOOR)LongMath.divide(int, int, RoundingMode.FLOOR) 。 (披露:我向番石榴捐款。)

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

n < 0d > 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)范围内[0, d)

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

对于负除数,公式并不是那么整洁。 以下是ifloordivifloormod扩展版本,它们遵循您的“好的”行为选项(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并且nInteger.MIN_VALUE时,存在不可避免的问题情况,因为那时数学结果溢出了该类型。 在这种情况下,上面的公式返回包装结果,就像通常的Java分区一样。 据我所知,这是唯一一个我们默默得到“错误”结果的角落案例。

(我正在做long的事情,因为int的答案是相同的,只需为每个long替换int ,并为每个Long替换Integer 。)

你可以只用Math.floor得到双除法结果,否则……

原始答案:

 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的答案我到目前为止最好的是:

 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对26))。

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