001/**
002 * The MIT License (MIT)
003 *
004 * Copyright (c) 2015-2016 decimal4j (tools4j), Marco Terzer
005 *
006 * Permission is hereby granted, free of charge, to any person obtaining a copy
007 * of this software and associated documentation files (the "Software"), to deal
008 * in the Software without restriction, including without limitation the rights
009 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
010 * copies of the Software, and to permit persons to whom the Software is
011 * furnished to do so, subject to the following conditions:
012 *
013 * The above copyright notice and this permission notice shall be included in all
014 * copies or substantial portions of the Software.
015 *
016 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
017 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
018 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
019 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
020 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
021 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
022 * SOFTWARE.
023 */
024package org.decimal4j.arithmetic;
025
026/**
027 * Helper class to emulate unsigned 64bit operations.
028 */
029public final class Unsigned {
030
031        /**
032         * A (self-inverse) bijection which converts the ordering on unsigned longs
033         * to the ordering on longs, that is, {@code a <= b} as unsigned longs if
034         * and only if {@code flip(a) <= flip(b)} as signed longs.
035         * <p>
036         * From Guava's <a href=
037         * "http://docs.guava-libraries.googlecode.com/git/javadoc/src-html/com/google/common/primitives/UnsignedLongs.html"
038         * >UnsignedLongs</a>.
039         * 
040         * @param a the unsigned long value to flip
041         * @return the flipped value
042         */
043        private static final long flip(long a) {
044                return a ^ Long.MIN_VALUE;
045        }
046
047        /**
048         * Compares the two specified {@code long} values, treating them as unsigned
049         * values between {@code 0} and {@code 2^64 - 1} inclusive.
050         * <p>
051         * From Guava's <a href=
052         * "http://docs.guava-libraries.googlecode.com/git/javadoc/src-html/com/google/common/primitives/UnsignedLongs.html"
053         * >UnsignedLongs</a>.
054         *
055         * @param a
056         *            the first unsigned {@code long} to compare
057         * @param b
058         *            the second unsigned {@code long} to compare
059         * @return a negative value if {@code a} is less than {@code b}; a positive
060         *         value if {@code a} is greater than {@code b}; or zero if they are
061         *         equal
062         */
063        public static final int compare(long a, long b) {
064                return Long.compare(flip(a), flip(b));
065        }
066
067        /**
068         * Compare two longs as if they were unsigned. Returns true iff one is
069         * bigger than two.
070         * 
071         * @param one
072         *            the first unsigned {@code long} to compare
073         * @param two
074         *            the second unsigned {@code long} to compare
075         * @return true if {@code one > two}
076         */
077        public static final boolean isGreater(long one, long two) {
078                return flip(one) > flip(two);
079        }
080
081        /**
082         * Compare two longs as if they were unsigned. Returns true iff one is
083         * smaller than two.
084         * 
085         * @param one
086         *            the first unsigned {@code long} to compare
087         * @param two
088         *            the second unsigned {@code long} to compare
089         * @return true if {@code one < two}
090         */
091        public static final boolean isLess(long one, long two) {
092                return flip(one) < flip(two);
093        }
094
095        /**
096         * Compare two longs as if they were unsigned. Returns true iff one is less
097         * than or equal to two.
098         * 
099         * @param one
100         *            the first unsigned {@code long} to compare
101         * @param two
102         *            the second unsigned {@code long} to compare
103         * @return true if {@code one <= two}
104         */
105        public static final boolean isLessOrEqual(long one, long two) {
106                return flip(one) <= flip(two);
107        }
108
109        /**
110         * Returns dividend / divisor, where the dividend and divisor are treated as
111         * unsigned 64-bit quantities.
112         *
113         * @param dividend
114         *            the dividend (numerator)
115         * @param divisor
116         *            the divisor (denominator)
117         * @return {@code dividend / divisor}
118         * @throws ArithmeticException
119         *             if divisor is 0
120         */
121        public static final long divide(long dividend, long divisor) {
122                if (divisor < 0) { // i.e., divisor >= 2^63:
123                        return compare(dividend, divisor) < 0 ? 0 : 1;
124                }
125
126                // Optimization - use signed division if dividend < 2^63
127                if (dividend >= 0) {
128                        return dividend / divisor;
129                }
130                // If divisor is even, we can divide both by 2
131                if (0 == (divisor & 0x1)) {
132                        return (dividend >>> 1) / (divisor >>> 1);
133                }
134
135                /*
136                 * Otherwise, approximate the quotient, check, and correct if necessary.
137                 * Our approximation is guaranteed to be either exact or one less than
138                 * the correct value. This follows from fact that floor(floor(x)/i) ==
139                 * floor(x/i) for any real x and integer i != 0. The proof is not quite
140                 * trivial.
141                 */
142                long quotient = ((dividend >>> 1) / divisor) << 1;
143                long rem = dividend - quotient * divisor;
144                return quotient + (isLess(rem, divisor) ? 0 : 1);
145        }
146
147        private Unsigned() {
148                // no instances
149        }
150
151}