Better implementation of Long.divideUnsigned and Long.remainderUnsigned

[John Platts]

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.