java Floored和大整数的欧几里得除法 1 周,1 日 Questions & Answers 332 Java的BigInteger类提供了截断除法(商和余数)。考虑到这一点,最简单、最有效的方法是什么来实现地板除法和欧几里得除法(商和余数)
# 1 楼答案 根据:https://stackoverflow.com/a/4110620/4701236这应该是相当有效的。注意,这是在C语言而不是Java语言中测试效率的,但是看到差异非常小,我不认为它们在Java语言中会有很大的差异(实现之间的差异,而不是C和Java之间的差异),因为当前的Java编译器优化了很多 public BigInteger euclidianDivision(BigInteger a,BigInteger b){ return (a - (a<0 ? b-1 : 0)).divide(b) } public BigInteger flooredDivision(BigInteger a,BigInteger b){ return (a + ( ((x<0) != (y<0))? b-1 : 0)).divide(b) } public BigInteger secondFlooredDivision(BigInteger a,BigInteger b){ return (a + ( ((a ^ b) < 0)? b-1 : 0)).divide(b) } SecondFloordDivision假设负数的二进制表示形式,所以我建议您使用另一种。目前无法测试这段代码,所以如果有人可以运行它并纠正可能的语法错误(我将其作为伪代码编写)
# 2 楼答案 根据Soronbe的答案,以下是正确Java语法的实现(不包括floored divison的第二个变体): public BigInteger euclidianDivision(BigInteger a, BigInteger b) { return a.subtract( a.compareTo(BigInteger.ZERO) < 0 ? b.subtract(BigInteger.ONE) : BigInteger.ZERO ).divide(b) } public BigInteger flooredDivision(BigInteger a, BigInteger b) { return a.add( (a.compareTo(BigInteger.ZERO) < 0) != (b.compareTo(BigInteger.ZERO) < 0) ? b.subtract(BigInteger.ONE) : BigInteger.ZERO ).divide(b); } 更新: 为了根据三种除法算法计算余数,其中两种算法已经在BigInteger(对于欧氏除法mod,对于截断除法remainder)中实现。要获得地板部门的剩余部分,可以使用以下实现: public BigInteger flooredRemainder(BigInteger a, BigInteger b) { return a.mod(b).subtract( b.compareTo(BigInteger.ZERO) < 0 ? BigInteger.ONE : BigInteger.ZERO ); }
# 1 楼答案
根据:https://stackoverflow.com/a/4110620/4701236这应该是相当有效的。注意,这是在C语言而不是Java语言中测试效率的,但是看到差异非常小,我不认为它们在Java语言中会有很大的差异(实现之间的差异,而不是C和Java之间的差异),因为当前的Java编译器优化了很多
SecondFloordDivision假设负数的二进制表示形式,所以我建议您使用另一种。目前无法测试这段代码,所以如果有人可以运行它并纠正可能的语法错误(我将其作为伪代码编写)
# 2 楼答案
根据Soronbe的答案,以下是正确Java语法的实现(不包括floored divison的第二个变体):
更新: 为了根据三种除法算法计算余数,其中两种算法已经在
BigInteger
(对于欧氏除法mod
,对于截断除法remainder
)中实现。要获得地板部门的剩余部分,可以使用以下实现: