In the implementations of Long.divideUnsigned and Long.remainderUnsigned, there
is a better way to handle the case where dividend > Long.MAX_VALUE and divisor
<= Long.MAX_VALUE than doing it through a BigInteger.
Here is the current implementation of Long.divideUnsigned and
Long.remainderUnsigned from OpenJDK 9:
/**
* Returns the unsigned quotient of dividing the first argument by
* the second where each argument and the result is interpreted as
* an unsigned value.
*
* <p>Note that in two's complement arithmetic, the three other
* basic arithmetic operations of add, subtract, and multiply are
* bit-wise identical if the two operands are regarded as both
* being signed or both being unsigned. Therefore separate {@code
* addUnsigned}, etc. methods are not provided.
*
* @param dividend the value to be divided
* @param divisor the value doing the dividing
* @return the unsigned quotient of the first argument divided by
* the second argument
* @see #remainderUnsigned
* @since 1.8
*/
public static long divideUnsigned(long dividend, long divisor) {
if (divisor < 0L) { // signed comparison
// Answer must be 0 or 1 depending on relative magnitude
// of dividend and divisor.
return (compareUnsigned(dividend, divisor)) < 0 ? 0L :1L;
}
if (dividend > 0) // Both inputs non-negative
return dividend/divisor;
else {
/*
* For simple code, leveraging BigInteger. Longer and faster
* code written directly in terms of operations on longs is
* possible; see "Hacker's Delight" for divide and remainder
* algorithms.
*/
return toUnsignedBigInteger(dividend).
divide(toUnsignedBigInteger(divisor)).longValue();
}
}
/**
* Returns the unsigned remainder from dividing the first argument
* by the second where each argument and the result is interpreted
* as an unsigned value.
*
* @param dividend the value to be divided
* @param divisor the value doing the dividing
* @return the unsigned remainder of the first argument divided by
* the second argument
* @see #divideUnsigned
* @since 1.8
*/
public static long remainderUnsigned(long dividend, long divisor) {
if (dividend > 0 && divisor > 0) { // signed comparisons
return dividend % divisor;
} else {
if (compareUnsigned(dividend, divisor) < 0) // Avoid explicit check
for 0 divisor
return dividend;
else
return toUnsignedBigInteger(dividend).
remainder(toUnsignedBigInteger(divisor)).longValue();
}
}
Here is an better implementation that does not require conversion to BigInteger:
/**
* Returns the unsigned quotient of dividing the first argument by
* the second where each argument and the result is interpreted as
* an unsigned value.
*
* <p>Note that in two's complement arithmetic, the three other
* basic arithmetic operations of add, subtract, and multiply are
* bit-wise identical if the two operands are regarded as both
* being signed or both being unsigned. Therefore separate {@code
* addUnsigned}, etc. methods are not provided.
*
* @param dividend the value to be divided
* @param divisor the value doing the dividing
* @return the unsigned quotient of the first argument divided by
* the second argument
* @see #remainderUnsigned
* @since 1.8
*/
public static long divideUnsigned(long dividend, long divisor) {
if (divisor < 0L) { // signed comparison
// Answer must be 0 or 1 depending on relative magnitude
// of dividend and divisor.
return (compareUnsigned(dividend, divisor)) < 0 ? 0L :1L;
}
if (dividend > 0 || divisor <= 1) {
// One of the following is true:
// 1. Both inputs are positive, in which the result is equal to
dividing
// dividend by divisor.
// 2. The divisor is equal to zero, which will result in a
DivideByZeroException
// being thrown.
// 3. The divisor is equal to one, in which the result is equal to
dividend.
return dividend/divisor;
} else {
long rMax = divisor - 1;
if(divisor != 0 && (divisor & rMax) == 0) { // divisor is power of 2
return dividend >>> Long.numberOfTrailingZeros(divisor);
}
// First, divide Long.MAX_VALUE + 1 by divisor.
// Division of Long.MAX_VALUE + 1 by divisor is done by the
following:
// 1. Dividing Long.MAX_VALUE by divisor
// 2. Computing the remainder of Long.MAX_VALUE by divisor
// 3. Adding 1 to the remainder computed in step #2.
// 4. If the remainder is equal to divisor, add 1 to the quotient
and set
// the remainder to zero.
long q = Long.MAX_VALUE / divisor;
long r = (Long.MAX_VALUE % divisor) + 1;
if(r == divisor) {
q++;
r = 0;
}
// Let x2 be equal to dividend - (Long.MAX_VALUE + 1).
// Compute the actual quotient and remainder of dividing dividend
by divisor
// by doing the following:
// 1. Increment q by the quotient of dividing x2 by divisor.
// 2. Increment r by the remainder of dividing x2 by divisor.
// 3. If r >= divisor is true, then increment q by 1 and decrement
r by divisor.
long x2 = dividend & Long.MAX_VALUE;
q += x2 / divisor;
r += x2 % divisor;
if(r >= divisor) {
q++;
r -= divisor;
}
// Return q, which is now the actual remainder of dividing dividend
by divisor.
return q;
}
}
/**
* Returns the unsigned remainder from dividing the first argument
* by the second where each argument and the result is interpreted
* as an unsigned value.
*
* @param dividend the value to be divided
* @param divisor the value doing the dividing
* @return the unsigned remainder of the first argument divided by
* the second argument
* @see #divideUnsigned
* @since 1.8
*/
public static long remainderUnsigned(long dividend, long divisor) {
if (dividend > 0 && divisor > 0) { // signed comparisons
return dividend % divisor;
} else {
if (compareUnsigned(dividend, divisor) < 0) { // Avoid explicit
check for 0 divisor
return dividend;
} else {
long rMax = divisor - 1;
if(divisor != 0 && (divisor & rMax) == 0) { // divisor is power
of 2
return dividend & rMax;
}
// First, compute the remainder of dividing Long.MAX_VALUE + 1
// This is done by doing the following:
// 1. Computing the remainder of dividing Long.MAX_VALUE by
divisor.
// 2. Adding 1 to the remainder computed in step #1.
// 3. If the remainder is equal to divisor, set the remainder
to 0.
long r = (Long.MAX_VALUE % divisor) + 1;
if(r == divisor) {
r = 0;
}
// Let x2 be equal to dividend - (Long.MAX_VALUE + 1).
// Compute the actual remainder of dividing dividend by divisor
// by doing the following:
// 1. Increment r by the remainder of dividing x2 by divisor.
// 2. If r >= divisor is true, then decrement r by divisor.
long x2 = dividend & Long.MAX_VALUE;
r += x2 % divisor;
if(r >= divisor) {
r -= divisor;
}
// Return r, which is now the actual remainder of dividing
dividend by divisor.
return r;
}
}
}
The updated implementations of divideUnsigned and remainderUnsigned avoid the
memory allocations that are involved in doing division through BigInteger. In
addition, the algorithm used to do division without going through a BigInteger
is simpler than the actual implementation in the BigInteger class.
