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 */ }
(更新:我想为int
和long
算法提供解决方案。)
如果你可以使用第三方库, Guava就有: IntMath.divide(int, int, RoundingMode.FLOOR)
和LongMath.divide(int, int, RoundingMode.FLOOR)
。 (披露:我向番石榴捐款。)
如果您不想为此使用第三方库,您仍然可以查看实现。
当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)
范围内[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分区一样。 据我所知,这是唯一一个我们默默得到“错误”结果的角落案例。
(我正在做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();