Source code

001/*
002 * Copyright (C) 2011 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
005 * in compliance with the License. You may obtain a copy of the License at
006 *
007 * http://www.apache.org/licenses/LICENSE-2.0
008 *
009 * Unless required by applicable law or agreed to in writing, software distributed under the License
010 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
011 * or implied. See the License for the specific language governing permissions and limitations under
012 * the License.
013 */
014
015package com.google.common.math;
016
017import static com.google.common.base.Preconditions.checkArgument;
018import static com.google.common.base.Preconditions.checkNotNull;
019import static com.google.common.math.MathPreconditions.checkNoOverflow;
020import static com.google.common.math.MathPreconditions.checkNonNegative;
021import static com.google.common.math.MathPreconditions.checkPositive;
022import static com.google.common.math.MathPreconditions.checkRoundingUnnecessary;
023import static java.lang.Math.abs;
024import static java.lang.Math.min;
025import static java.math.RoundingMode.HALF_EVEN;
026import static java.math.RoundingMode.HALF_UP;
027
028import com.google.common.annotations.Beta;
029import com.google.common.annotations.GwtCompatible;
030import com.google.common.annotations.GwtIncompatible;
031import com.google.common.annotations.VisibleForTesting;
032import com.google.common.primitives.Longs;
033import com.google.common.primitives.UnsignedLongs;
034import java.math.BigInteger;
035import java.math.RoundingMode;
036
037/**
038 * A class for arithmetic on values of type {@code long}. Where possible, methods are defined and
039 * named analogously to their {@code BigInteger} counterparts.
040 *
041 * <p>The implementations of many methods in this class are based on material from Henry S. Warren,
042 * Jr.'s <i>Hacker's Delight</i>, (Addison Wesley, 2002).
043 *
044 * <p>Similar functionality for {@code int} and for {@link BigInteger} can be found in {@link
045 * IntMath} and {@link BigIntegerMath} respectively. For other common operations on {@code long}
046 * values, see {@link com.google.common.primitives.Longs}.
047 *
048 * @author Louis Wasserman
049 * @since 11.0
050 */
051@GwtCompatible(emulated = true)
052@ElementTypesAreNonnullByDefault
053public final class LongMath {
054  // NOTE: Whenever both tests are cheap and functional, it's faster to use &, | instead of &&, ||
055
056  @VisibleForTesting static final long MAX_SIGNED_POWER_OF_TWO = 1L << (Long.SIZE - 2);
057
058  /**
059   * Returns the smallest power of two greater than or equal to {@code x}. This is equivalent to
060   * {@code checkedPow(2, log2(x, CEILING))}.
061   *
062   * @throws IllegalArgumentException if {@code x <= 0}
063   * @throws ArithmeticException of the next-higher power of two is not representable as a {@code
064   *     long}, i.e. when {@code x > 2^62}
065   * @since 20.0
066   */
067  @Beta
068  public static long ceilingPowerOfTwo(long x) {
069    checkPositive("x", x);
070    if (x > MAX_SIGNED_POWER_OF_TWO) {
071      throw new ArithmeticException("ceilingPowerOfTwo(" + x + ") is not representable as a long");
072    }
073    return 1L << -Long.numberOfLeadingZeros(x - 1);
074  }
075
076  /**
077   * Returns the largest power of two less than or equal to {@code x}. This is equivalent to {@code
078   * checkedPow(2, log2(x, FLOOR))}.
079   *
080   * @throws IllegalArgumentException if {@code x <= 0}
081   * @since 20.0
082   */
083  @Beta
084  public static long floorPowerOfTwo(long x) {
085    checkPositive("x", x);
086
087    // Long.highestOneBit was buggy on GWT.  We've fixed it, but I'm not certain when the fix will
088    // be released.
089    return 1L << ((Long.SIZE - 1) - Long.numberOfLeadingZeros(x));
090  }
091
092  /**
093   * Returns {@code true} if {@code x} represents a power of two.
094   *
095   * <p>This differs from {@code Long.bitCount(x) == 1}, because {@code
096   * Long.bitCount(Long.MIN_VALUE) == 1}, but {@link Long#MIN_VALUE} is not a power of two.
097   */
098  public static boolean isPowerOfTwo(long x) {
099    return x > 0 & (x & (x - 1)) == 0;
100  }
101
102  /**
103   * Returns 1 if {@code x < y} as unsigned longs, and 0 otherwise. Assumes that x - y fits into a
104   * signed long. The implementation is branch-free, and benchmarks suggest it is measurably faster
105   * than the straightforward ternary expression.
106   */
107  @VisibleForTesting
108  static int lessThanBranchFree(long x, long y) {
109    // Returns the sign bit of x - y.
110    return (int) (~~(x - y) >>> (Long.SIZE - 1));
111  }
112
113  /**
114   * Returns the base-2 logarithm of {@code x}, rounded according to the specified rounding mode.
115   *
116   * @throws IllegalArgumentException if {@code x <= 0}
117   * @throws ArithmeticException if {@code mode} is {@link RoundingMode#UNNECESSARY} and {@code x}
118   *     is not a power of two
119   */
120  @SuppressWarnings("fallthrough")
121  // TODO(kevinb): remove after this warning is disabled globally
122  public static int log2(long x, RoundingMode mode) {
123    checkPositive("x", x);
124    switch (mode) {
125      case UNNECESSARY:
126        checkRoundingUnnecessary(isPowerOfTwo(x));
127        // fall through
128      case DOWN:
129      case FLOOR:
130        return (Long.SIZE - 1) - Long.numberOfLeadingZeros(x);
131
132      case UP:
133      case CEILING:
134        return Long.SIZE - Long.numberOfLeadingZeros(x - 1);
135
136      case HALF_DOWN:
137      case HALF_UP:
138      case HALF_EVEN:
139        // Since sqrt(2) is irrational, log2(x) - logFloor cannot be exactly 0.5
140        int leadingZeros = Long.numberOfLeadingZeros(x);
141        long cmp = MAX_POWER_OF_SQRT2_UNSIGNED >>> leadingZeros;
142        // floor(2^(logFloor + 0.5))
143        int logFloor = (Long.SIZE - 1) - leadingZeros;
144        return logFloor + lessThanBranchFree(cmp, x);
145
146      default:
147        throw new AssertionError("impossible");
148    }
149  }
150
151  /** The biggest half power of two that fits into an unsigned long */
152  @VisibleForTesting static final long MAX_POWER_OF_SQRT2_UNSIGNED = 0xB504F333F9DE6484L;
153
154  /**
155   * Returns the base-10 logarithm of {@code x}, rounded according to the specified rounding mode.
156   *
157   * @throws IllegalArgumentException if {@code x <= 0}
158   * @throws ArithmeticException if {@code mode} is {@link RoundingMode#UNNECESSARY} and {@code x}
159   *     is not a power of ten
160   */
161  @GwtIncompatible // TODO
162  @SuppressWarnings("fallthrough")
163  // TODO(kevinb): remove after this warning is disabled globally
164  public static int log10(long x, RoundingMode mode) {
165    checkPositive("x", x);
166    int logFloor = log10Floor(x);
167    long floorPow = powersOf10[logFloor];
168    switch (mode) {
169      case UNNECESSARY:
170        checkRoundingUnnecessary(x == floorPow);
171        // fall through
172      case FLOOR:
173      case DOWN:
174        return logFloor;
175      case CEILING:
176      case UP:
177        return logFloor + lessThanBranchFree(floorPow, x);
178      case HALF_DOWN:
179      case HALF_UP:
180      case HALF_EVEN:
181        // sqrt(10) is irrational, so log10(x)-logFloor is never exactly 0.5
182        return logFloor + lessThanBranchFree(halfPowersOf10[logFloor], x);
183      default:
184        throw new AssertionError();
185    }
186  }
187
188  @GwtIncompatible // TODO
189  static int log10Floor(long x) {
190    /*
191     * Based on Hacker's Delight Fig. 11-5, the two-table-lookup, branch-free implementation.
192     *
193     * The key idea is that based on the number of leading zeros (equivalently, floor(log2(x))), we
194     * can narrow the possible floor(log10(x)) values to two. For example, if floor(log2(x)) is 6,
195     * then 64 <= x < 128, so floor(log10(x)) is either 1 or 2.
196     */
197    int y = maxLog10ForLeadingZeros[Long.numberOfLeadingZeros(x)];
198    /*
199     * y is the higher of the two possible values of floor(log10(x)). If x < 10^y, then we want the
200     * lower of the two possible values, or y - 1, otherwise, we want y.
201     */
202    return y - lessThanBranchFree(x, powersOf10[y]);
203  }
204
205  // maxLog10ForLeadingZeros[i] == floor(log10(2^(Long.SIZE - i)))
206  @VisibleForTesting
207  static final byte[] maxLog10ForLeadingZeros = {
208    19, 18, 18, 18, 18, 17, 17, 17, 16, 16, 16, 15, 15, 15, 15, 14, 14, 14, 13, 13, 13, 12, 12, 12,
209    12, 11, 11, 11, 10, 10, 10, 9, 9, 9, 9, 8, 8, 8, 7, 7, 7, 6, 6, 6, 6, 5, 5, 5, 4, 4, 4, 3, 3, 3,
210    3, 2, 2, 2, 1, 1, 1, 0, 0, 0
211  };
212
213  @GwtIncompatible // TODO
214  @VisibleForTesting
215  static final long[] powersOf10 = {
216    1L,
217    10L,
218    100L,
219    1000L,
220    10000L,
221    100000L,
222    1000000L,
223    10000000L,
224    100000000L,
225    1000000000L,
226    10000000000L,
227    100000000000L,
228    1000000000000L,
229    10000000000000L,
230    100000000000000L,
231    1000000000000000L,
232    10000000000000000L,
233    100000000000000000L,
234    1000000000000000000L
235  };
236
237  // halfPowersOf10[i] = largest long less than 10^(i + 0.5)
238  @GwtIncompatible // TODO
239  @VisibleForTesting
240  static final long[] halfPowersOf10 = {
241    3L,
242    31L,
243    316L,
244    3162L,
245    31622L,
246    316227L,
247    3162277L,
248    31622776L,
249    316227766L,
250    3162277660L,
251    31622776601L,
252    316227766016L,
253    3162277660168L,
254    31622776601683L,
255    316227766016837L,
256    3162277660168379L,
257    31622776601683793L,
258    316227766016837933L,
259    3162277660168379331L
260  };
261
262  /**
263   * Returns {@code b} to the {@code k}th power. Even if the result overflows, it will be equal to
264   * {@code BigInteger.valueOf(b).pow(k).longValue()}. This implementation runs in {@code O(log k)}
265   * time.
266   *
267   * @throws IllegalArgumentException if {@code k < 0}
268   */
269  @GwtIncompatible // TODO
270  public static long pow(long b, int k) {
271    checkNonNegative("exponent", k);
272    if (-2 <= b && b <= 2) {
273      switch ((int) b) {
274        case 0:
275          return (k == 0) ? 1 : 0;
276        case 1:
277          return 1;
278        case (-1):
279          return ((k & 1) == 0) ? 1 : -1;
280        case 2:
281          return (k < Long.SIZE) ? 1L << k : 0;
282        case (-2):
283          if (k < Long.SIZE) {
284            return ((k & 1) == 0) ? 1L << k : -(1L << k);
285          } else {
286            return 0;
287          }
288        default:
289          throw new AssertionError();
290      }
291    }
292    for (long accum = 1; ; k >>= 1) {
293      switch (k) {
294        case 0:
295          return accum;
296        case 1:
297          return accum * b;
298        default:
299          accum *= ((k & 1) == 0) ? 1 : b;
300          b *= b;
301      }
302    }
303  }
304
305  /**
306   * Returns the square root of {@code x}, rounded with the specified rounding mode.
307   *
308   * @throws IllegalArgumentException if {@code x < 0}
309   * @throws ArithmeticException if {@code mode} is {@link RoundingMode#UNNECESSARY} and {@code
310   *     sqrt(x)} is not an integer
311   */
312  @GwtIncompatible // TODO
313  @SuppressWarnings("fallthrough")
314  public static long sqrt(long x, RoundingMode mode) {
315    checkNonNegative("x", x);
316    if (fitsInInt(x)) {
317      return IntMath.sqrt((int) x, mode);
318    }
319    /*
320     * Let k be the true value of floor(sqrt(x)), so that
321     *
322     *            k * k <= x          <  (k + 1) * (k + 1)
323     * (double) (k * k) <= (double) x <= (double) ((k + 1) * (k + 1))
324     *          since casting to double is nondecreasing.
325     *          Note that the right-hand inequality is no longer strict.
326     * Math.sqrt(k * k) <= Math.sqrt(x) <= Math.sqrt((k + 1) * (k + 1))
327     *          since Math.sqrt is monotonic.
328     * (long) Math.sqrt(k * k) <= (long) Math.sqrt(x) <= (long) Math.sqrt((k + 1) * (k + 1))
329     *          since casting to long is monotonic
330     * k <= (long) Math.sqrt(x) <= k + 1
331     *          since (long) Math.sqrt(k * k) == k, as checked exhaustively in
332     *          {@link LongMathTest#testSqrtOfPerfectSquareAsDoubleIsPerfect}
333     */
334    long guess = (long) Math.sqrt(x);
335    // Note: guess is always <= FLOOR_SQRT_MAX_LONG.
336    long guessSquared = guess * guess;
337    // Note (2013-2-26): benchmarks indicate that, inscrutably enough, using if statements is
338    // faster here than using lessThanBranchFree.
339    switch (mode) {
340      case UNNECESSARY:
341        checkRoundingUnnecessary(guessSquared == x);
342        return guess;
343      case FLOOR:
344      case DOWN:
345        if (x < guessSquared) {
346          return guess - 1;
347        }
348        return guess;
349      case CEILING:
350      case UP:
351        if (x > guessSquared) {
352          return guess + 1;
353        }
354        return guess;
355      case HALF_DOWN:
356      case HALF_UP:
357      case HALF_EVEN:
358        long sqrtFloor = guess - ((x < guessSquared) ? 1 : 0);
359        long halfSquare = sqrtFloor * sqrtFloor + sqrtFloor;
360        /*
361         * We wish to test whether or not x <= (sqrtFloor + 0.5)^2 = halfSquare + 0.25. Since both x
362         * and halfSquare are integers, this is equivalent to testing whether or not x <=
363         * halfSquare. (We have to deal with overflow, though.)
364         *
365         * If we treat halfSquare as an unsigned long, we know that
366         *            sqrtFloor^2 <= x < (sqrtFloor + 1)^2
367         * halfSquare - sqrtFloor <= x < halfSquare + sqrtFloor + 1
368         * so |x - halfSquare| <= sqrtFloor.  Therefore, it's safe to treat x - halfSquare as a
369         * signed long, so lessThanBranchFree is safe for use.
370         */
371        return sqrtFloor + lessThanBranchFree(halfSquare, x);
372      default:
373        throw new AssertionError();
374    }
375  }
376
377  /**
378   * Returns the result of dividing {@code p} by {@code q}, rounding using the specified {@code
379   * RoundingMode}.
380   *
381   * @throws ArithmeticException if {@code q == 0}, or if {@code mode == UNNECESSARY} and {@code a}
382   *     is not an integer multiple of {@code b}
383   */
384  @GwtIncompatible // TODO
385  @SuppressWarnings("fallthrough")
386  public static long divide(long p, long q, RoundingMode mode) {
387    checkNotNull(mode);
388    long div = p / q; // throws if q == 0
389    long rem = p - q * div; // equals p % q
390
391    if (rem == 0) {
392      return div;
393    }
394
395    /*
396     * Normal Java division rounds towards 0, consistently with RoundingMode.DOWN. We just have to
397     * deal with the cases where rounding towards 0 is wrong, which typically depends on the sign of
398     * p / q.
399     *
400     * signum is 1 if p and q are both nonnegative or both negative, and -1 otherwise.
401     */
402    int signum = 1 | (int) ((p ^ q) >> (Long.SIZE - 1));
403    boolean increment;
404    switch (mode) {
405      case UNNECESSARY:
406        checkRoundingUnnecessary(rem == 0);
407        // fall through
408      case DOWN:
409        increment = false;
410        break;
411      case UP:
412        increment = true;
413        break;
414      case CEILING:
415        increment = signum > 0;
416        break;
417      case FLOOR:
418        increment = signum < 0;
419        break;
420      case HALF_EVEN:
421      case HALF_DOWN:
422      case HALF_UP:
423        long absRem = abs(rem);
424        long cmpRemToHalfDivisor = absRem - (abs(q) - absRem);
425        // subtracting two nonnegative longs can't overflow
426        // cmpRemToHalfDivisor has the same sign as compare(abs(rem), abs(q) / 2).
427        if (cmpRemToHalfDivisor == 0) { // exactly on the half mark
428          increment = (mode == HALF_UP || (mode == HALF_EVEN && (div & 1) != 0));
429        } else {
430          increment = cmpRemToHalfDivisor > 0; // closer to the UP value
431        }
432        break;
433      default:
434        throw new AssertionError();
435    }
436    return increment ? div + signum : div;
437  }
438
439  /**
440   * Returns {@code x mod m}, a non-negative value less than {@code m}. This differs from {@code x %
441   * m}, which might be negative.
442   *
443   * <p>For example:
444   *
445   * <pre>{@code
446   * mod(7, 4) == 3
447   * mod(-7, 4) == 1
448   * mod(-1, 4) == 3
449   * mod(-8, 4) == 0
450   * mod(8, 4) == 0
451   * }</pre>
452   *
453   * @throws ArithmeticException if {@code m <= 0}
454   * @see <a href="http://docs.oracle.com/javase/specs/jls/se7/html/jls-15.html#jls-15.17.3">
455   *     Remainder Operator</a>
456   */
457  @GwtIncompatible // TODO
458  public static int mod(long x, int m) {
459    // Cast is safe because the result is guaranteed in the range [0, m)
460    return (int) mod(x, (long) m);
461  }
462
463  /**
464   * Returns {@code x mod m}, a non-negative value less than {@code m}. This differs from {@code x %
465   * m}, which might be negative.
466   *
467   * <p>For example:
468   *
469   * <pre>{@code
470   * mod(7, 4) == 3
471   * mod(-7, 4) == 1
472   * mod(-1, 4) == 3
473   * mod(-8, 4) == 0
474   * mod(8, 4) == 0
475   * }</pre>
476   *
477   * @throws ArithmeticException if {@code m <= 0}
478   * @see <a href="http://docs.oracle.com/javase/specs/jls/se7/html/jls-15.html#jls-15.17.3">
479   *     Remainder Operator</a>
480   */
481  @GwtIncompatible // TODO
482  public static long mod(long x, long m) {
483    if (m <= 0) {
484      throw new ArithmeticException("Modulus must be positive");
485    }
486    long result = x % m;
487    return (result >= 0) ? result : result + m;
488  }
489
490  /**
491   * Returns the greatest common divisor of {@code a, b}. Returns {@code 0} if {@code a == 0 && b ==
492   * 0}.
493   *
494   * @throws IllegalArgumentException if {@code a < 0} or {@code b < 0}
495   */
496  public static long gcd(long a, long b) {
497    /*
498     * The reason we require both arguments to be >= 0 is because otherwise, what do you return on
499     * gcd(0, Long.MIN_VALUE)? BigInteger.gcd would return positive 2^63, but positive 2^63 isn't an
500     * int.
501     */
502    checkNonNegative("a", a);
503    checkNonNegative("b", b);
504    if (a == 0) {
505      // 0 % b == 0, so b divides a, but the converse doesn't hold.
506      // BigInteger.gcd is consistent with this decision.
507      return b;
508    } else if (b == 0) {
509      return a; // similar logic
510    }
511    /*
512     * Uses the binary GCD algorithm; see http://en.wikipedia.org/wiki/Binary_GCD_algorithm. This is
513     * >60% faster than the Euclidean algorithm in benchmarks.
514     */
515    int aTwos = Long.numberOfTrailingZeros(a);
516    a >>= aTwos; // divide out all 2s
517    int bTwos = Long.numberOfTrailingZeros(b);
518    b >>= bTwos; // divide out all 2s
519    while (a != b) { // both a, b are odd
520      // The key to the binary GCD algorithm is as follows:
521      // Both a and b are odd. Assume a > b; then gcd(a - b, b) = gcd(a, b).
522      // But in gcd(a - b, b), a - b is even and b is odd, so we can divide out powers of two.
523
524      // We bend over backwards to avoid branching, adapting a technique from
525      // http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax
526
527      long delta = a - b; // can't overflow, since a and b are nonnegative
528
529      long minDeltaOrZero = delta & (delta >> (Long.SIZE - 1));
530      // equivalent to Math.min(delta, 0)
531
532      a = delta - minDeltaOrZero - minDeltaOrZero; // sets a to Math.abs(a - b)
533      // a is now nonnegative and even
534
535      b += minDeltaOrZero; // sets b to min(old a, b)
536      a >>= Long.numberOfTrailingZeros(a); // divide out all 2s, since 2 doesn't divide b
537    }
538    return a << min(aTwos, bTwos);
539  }
540
541  /**
542   * Returns the sum of {@code a} and {@code b}, provided it does not overflow.
543   *
544   * @throws ArithmeticException if {@code a + b} overflows in signed {@code long} arithmetic
545   */
546  public static long checkedAdd(long a, long b) {
547    long result = a + b;
548    checkNoOverflow((a ^ b) < 0 | (a ^ result) >= 0, "checkedAdd", a, b);
549    return result;
550  }
551
552  /**
553   * Returns the difference of {@code a} and {@code b}, provided it does not overflow.
554   *
555   * @throws ArithmeticException if {@code a - b} overflows in signed {@code long} arithmetic
556   */
557  @GwtIncompatible // TODO
558  public static long checkedSubtract(long a, long b) {
559    long result = a - b;
560    checkNoOverflow((a ^ b) >= 0 | (a ^ result) >= 0, "checkedSubtract", a, b);
561    return result;
562  }
563
564  /**
565   * Returns the product of {@code a} and {@code b}, provided it does not overflow.
566   *
567   * @throws ArithmeticException if {@code a * b} overflows in signed {@code long} arithmetic
568   */
569  public static long checkedMultiply(long a, long b) {
570    // Hacker's Delight, Section 2-12
571    int leadingZeros =
572        Long.numberOfLeadingZeros(a)
573            + Long.numberOfLeadingZeros(~a)
574            + Long.numberOfLeadingZeros(b)
575            + Long.numberOfLeadingZeros(~b);
576    /*
577     * If leadingZeros > Long.SIZE + 1 it's definitely fine, if it's < Long.SIZE it's definitely
578     * bad. We do the leadingZeros check to avoid the division below if at all possible.
579     *
580     * Otherwise, if b == Long.MIN_VALUE, then the only allowed values of a are 0 and 1. We take
581     * care of all a < 0 with their own check, because in particular, the case a == -1 will
582     * incorrectly pass the division check below.
583     *
584     * In all other cases, we check that either a is 0 or the result is consistent with division.
585     */
586    if (leadingZeros > Long.SIZE + 1) {
587      return a * b;
588    }
589    checkNoOverflow(leadingZeros >= Long.SIZE, "checkedMultiply", a, b);
590    checkNoOverflow(a >= 0 | b != Long.MIN_VALUE, "checkedMultiply", a, b);
591    long result = a * b;
592    checkNoOverflow(a == 0 || result / a == b, "checkedMultiply", a, b);
593    return result;
594  }
595
596  /**
597   * Returns the {@code b} to the {@code k}th power, provided it does not overflow.
598   *
599   * @throws ArithmeticException if {@code b} to the {@code k}th power overflows in signed {@code
600   *     long} arithmetic
601   */
602  @GwtIncompatible // TODO
603  public static long checkedPow(long b, int k) {
604    checkNonNegative("exponent", k);
605    if (b >= -2 & b <= 2) {
606      switch ((int) b) {
607        case 0:
608          return (k == 0) ? 1 : 0;
609        case 1:
610          return 1;
611        case (-1):
612          return ((k & 1) == 0) ? 1 : -1;
613        case 2:
614          checkNoOverflow(k < Long.SIZE - 1, "checkedPow", b, k);
615          return 1L << k;
616        case (-2):
617          checkNoOverflow(k < Long.SIZE, "checkedPow", b, k);
618          return ((k & 1) == 0) ? (1L << k) : (-1L << k);
619        default:
620          throw new AssertionError();
621      }
622    }
623    long accum = 1;
624    while (true) {
625      switch (k) {
626        case 0:
627          return accum;
628        case 1:
629          return checkedMultiply(accum, b);
630        default:
631          if ((k & 1) != 0) {
632            accum = checkedMultiply(accum, b);
633          }
634          k >>= 1;
635          if (k > 0) {
636            checkNoOverflow(
637                -FLOOR_SQRT_MAX_LONG <= b && b <= FLOOR_SQRT_MAX_LONG, "checkedPow", b, k);
638            b *= b;
639          }
640      }
641    }
642  }
643
644  /**
645   * Returns the sum of {@code a} and {@code b} unless it would overflow or underflow in which case
646   * {@code Long.MAX_VALUE} or {@code Long.MIN_VALUE} is returned, respectively.
647   *
648   * @since 20.0
649   */
650  @Beta
651  public static long saturatedAdd(long a, long b) {
652    long naiveSum = a + b;
653    if ((a ^ b) < 0 | (a ^ naiveSum) >= 0) {
654      // If a and b have different signs or a has the same sign as the result then there was no
655      // overflow, return.
656      return naiveSum;
657    }
658    // we did over/under flow, if the sign is negative we should return MAX otherwise MIN
659    return Long.MAX_VALUE + ((naiveSum >>> (Long.SIZE - 1)) ^ 1);
660  }
661
662  /**
663   * Returns the difference of {@code a} and {@code b} unless it would overflow or underflow in
664   * which case {@code Long.MAX_VALUE} or {@code Long.MIN_VALUE} is returned, respectively.
665   *
666   * @since 20.0
667   */
668  @Beta
669  public static long saturatedSubtract(long a, long b) {
670    long naiveDifference = a - b;
671    if ((a ^ b) >= 0 | (a ^ naiveDifference) >= 0) {
672      // If a and b have the same signs or a has the same sign as the result then there was no
673      // overflow, return.
674      return naiveDifference;
675    }
676    // we did over/under flow
677    return Long.MAX_VALUE + ((naiveDifference >>> (Long.SIZE - 1)) ^ 1);
678  }
679
680  /**
681   * Returns the product of {@code a} and {@code b} unless it would overflow or underflow in which
682   * case {@code Long.MAX_VALUE} or {@code Long.MIN_VALUE} is returned, respectively.
683   *
684   * @since 20.0
685   */
686  @Beta
687  public static long saturatedMultiply(long a, long b) {
688    // see checkedMultiply for explanation
689    int leadingZeros =
690        Long.numberOfLeadingZeros(a)
691            + Long.numberOfLeadingZeros(~a)
692            + Long.numberOfLeadingZeros(b)
693            + Long.numberOfLeadingZeros(~b);
694    if (leadingZeros > Long.SIZE + 1) {
695      return a * b;
696    }
697    // the return value if we will overflow (which we calculate by overflowing a long :) )
698    long limit = Long.MAX_VALUE + ((a ^ b) >>> (Long.SIZE - 1));
699    if (leadingZeros < Long.SIZE | (a < 0 & b == Long.MIN_VALUE)) {
700      // overflow
701      return limit;
702    }
703    long result = a * b;
704    if (a == 0 || result / a == b) {
705      return result;
706    }
707    return limit;
708  }
709
710  /**
711   * Returns the {@code b} to the {@code k}th power, unless it would overflow or underflow in which
712   * case {@code Long.MAX_VALUE} or {@code Long.MIN_VALUE} is returned, respectively.
713   *
714   * @since 20.0
715   */
716  @Beta
717  public static long saturatedPow(long b, int k) {
718    checkNonNegative("exponent", k);
719    if (b >= -2 & b <= 2) {
720      switch ((int) b) {
721        case 0:
722          return (k == 0) ? 1 : 0;
723        case 1:
724          return 1;
725        case (-1):
726          return ((k & 1) == 0) ? 1 : -1;
727        case 2:
728          if (k >= Long.SIZE - 1) {
729            return Long.MAX_VALUE;
730          }
731          return 1L << k;
732        case (-2):
733          if (k >= Long.SIZE) {
734            return Long.MAX_VALUE + (k & 1);
735          }
736          return ((k & 1) == 0) ? (1L << k) : (-1L << k);
737        default:
738          throw new AssertionError();
739      }
740    }
741    long accum = 1;
742    // if b is negative and k is odd then the limit is MIN otherwise the limit is MAX
743    long limit = Long.MAX_VALUE + ((b >>> Long.SIZE - 1) & (k & 1));
744    while (true) {
745      switch (k) {
746        case 0:
747          return accum;
748        case 1:
749          return saturatedMultiply(accum, b);
750        default:
751          if ((k & 1) != 0) {
752            accum = saturatedMultiply(accum, b);
753          }
754          k >>= 1;
755          if (k > 0) {
756            if (-FLOOR_SQRT_MAX_LONG > b | b > FLOOR_SQRT_MAX_LONG) {
757              return limit;
758            }
759            b *= b;
760          }
761      }
762    }
763  }
764
765  @VisibleForTesting static final long FLOOR_SQRT_MAX_LONG = 3037000499L;
766
767  /**
768   * Returns {@code n!}, that is, the product of the first {@code n} positive integers, {@code 1} if
769   * {@code n == 0}, or {@link Long#MAX_VALUE} if the result does not fit in a {@code long}.
770   *
771   * @throws IllegalArgumentException if {@code n < 0}
772   */
773  @GwtIncompatible // TODO
774  public static long factorial(int n) {
775    checkNonNegative("n", n);
776    return (n < factorials.length) ? factorials[n] : Long.MAX_VALUE;
777  }
778
779  static final long[] factorials = {
780    1L,
781    1L,
782    1L * 2,
783    1L * 2 * 3,
784    1L * 2 * 3 * 4,
785    1L * 2 * 3 * 4 * 5,
786    1L * 2 * 3 * 4 * 5 * 6,
787    1L * 2 * 3 * 4 * 5 * 6 * 7,
788    1L * 2 * 3 * 4 * 5 * 6 * 7 * 8,
789    1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9,
790    1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10,
791    1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11,
792    1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12,
793    1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13,
794    1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14,
795    1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15,
796    1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16,
797    1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17,
798    1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17 * 18,
799    1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17 * 18 * 19,
800    1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17 * 18 * 19 * 20
801  };
802
803  /**
804   * Returns {@code n} choose {@code k}, also known as the binomial coefficient of {@code n} and
805   * {@code k}, or {@link Long#MAX_VALUE} if the result does not fit in a {@code long}.
806   *
807   * @throws IllegalArgumentException if {@code n < 0}, {@code k < 0}, or {@code k > n}
808   */
809  public static long binomial(int n, int k) {
810    checkNonNegative("n", n);
811    checkNonNegative("k", k);
812    checkArgument(k <= n, "k (%s) > n (%s)", k, n);
813    if (k > (n >> 1)) {
814      k = n - k;
815    }
816    switch (k) {
817      case 0:
818        return 1;
819      case 1:
820        return n;
821      default:
822        if (n < factorials.length) {
823          return factorials[n] / (factorials[k] * factorials[n - k]);
824        } else if (k >= biggestBinomials.length || n > biggestBinomials[k]) {
825          return Long.MAX_VALUE;
826        } else if (k < biggestSimpleBinomials.length && n <= biggestSimpleBinomials[k]) {
827          // guaranteed not to overflow
828          long result = n--;
829          for (int i = 2; i <= k; n--, i++) {
830            result *= n;
831            result /= i;
832          }
833          return result;
834        } else {
835          int nBits = LongMath.log2(n, RoundingMode.CEILING);
836
837          long result = 1;
838          long numerator = n--;
839          long denominator = 1;
840
841          int numeratorBits = nBits;
842          // This is an upper bound on log2(numerator, ceiling).
843
844          /*
845           * We want to do this in long math for speed, but want to avoid overflow. We adapt the
846           * technique previously used by BigIntegerMath: maintain separate numerator and
847           * denominator accumulators, multiplying the fraction into result when near overflow.
848           */
849          for (int i = 2; i <= k; i++, n--) {
850            if (numeratorBits + nBits < Long.SIZE - 1) {
851              // It's definitely safe to multiply into numerator and denominator.
852              numerator *= n;
853              denominator *= i;
854              numeratorBits += nBits;
855            } else {
856              // It might not be safe to multiply into numerator and denominator,
857              // so multiply (numerator / denominator) into result.
858              result = multiplyFraction(result, numerator, denominator);
859              numerator = n;
860              denominator = i;
861              numeratorBits = nBits;
862            }
863          }
864          return multiplyFraction(result, numerator, denominator);
865        }
866    }
867  }
868
869  /** Returns (x * numerator / denominator), which is assumed to come out to an integral value. */
870  static long multiplyFraction(long x, long numerator, long denominator) {
871    if (x == 1) {
872      return numerator / denominator;
873    }
874    long commonDivisor = gcd(x, denominator);
875    x /= commonDivisor;
876    denominator /= commonDivisor;
877    // We know gcd(x, denominator) = 1, and x * numerator / denominator is exact,
878    // so denominator must be a divisor of numerator.
879    return x * (numerator / denominator);
880  }
881
882  /*
883   * binomial(biggestBinomials[k], k) fits in a long, but not binomial(biggestBinomials[k] + 1, k).
884   */
885  static final int[] biggestBinomials = {
886    Integer.MAX_VALUE,
887    Integer.MAX_VALUE,
888    Integer.MAX_VALUE,
889    3810779,
890    121977,
891    16175,
892    4337,
893    1733,
894    887,
895    534,
896    361,
897    265,
898    206,
899    169,
900    143,
901    125,
902    111,
903    101,
904    94,
905    88,
906    83,
907    79,
908    76,
909    74,
910    72,
911    70,
912    69,
913    68,
914    67,
915    67,
916    66,
917    66,
918    66,
919    66
920  };
921
922  /*
923   * binomial(biggestSimpleBinomials[k], k) doesn't need to use the slower GCD-based impl, but
924   * binomial(biggestSimpleBinomials[k] + 1, k) does.
925   */
926  @VisibleForTesting
927  static final int[] biggestSimpleBinomials = {
928    Integer.MAX_VALUE,
929    Integer.MAX_VALUE,
930    Integer.MAX_VALUE,
931    2642246,
932    86251,
933    11724,
934    3218,
935    1313,
936    684,
937    419,
938    287,
939    214,
940    169,
941    139,
942    119,
943    105,
944    95,
945    87,
946    81,
947    76,
948    73,
949    70,
950    68,
951    66,
952    64,
953    63,
954    62,
955    62,
956    61,
957    61,
958    61
959  };
960  // These values were generated by using checkedMultiply to see when the simple multiply/divide
961  // algorithm would lead to an overflow.
962
963  static boolean fitsInInt(long x) {
964    return (int) x == x;
965  }
966
967  /**
968   * Returns the arithmetic mean of {@code x} and {@code y}, rounded toward negative infinity. This
969   * method is resilient to overflow.
970   *
971   * @since 14.0
972   */
973  public static long mean(long x, long y) {
974    // Efficient method for computing the arithmetic mean.
975    // The alternative (x + y) / 2 fails for large values.
976    // The alternative (x + y) >>> 1 fails for negative values.
977    return (x & y) + ((x ^ y) >> 1);
978  }
979
980  /*
981   * This bitmask is used as an optimization for cheaply testing for divisiblity by 2, 3, or 5.
982   * Each bit is set to 1 for all remainders that indicate divisibility by 2, 3, or 5, so
983   * 1, 7, 11, 13, 17, 19, 23, 29 are set to 0. 30 and up don't matter because they won't be hit.
984   */
985  private static final int SIEVE_30 =
986      ~((1 << 1) | (1 << 7) | (1 << 11) | (1 << 13) | (1 << 17) | (1 << 19) | (1 << 23)
987          | (1 << 29));
988
989  /**
990   * Returns {@code true} if {@code n} is a <a
991   * href="http://mathworld.wolfram.com/PrimeNumber.html">prime number</a>: an integer <i>greater
992   * than one</i> that cannot be factored into a product of <i>smaller</i> positive integers.
993   * Returns {@code false} if {@code n} is zero, one, or a composite number (one which <i>can</i> be
994   * factored into smaller positive integers).
995   *
996   * <p>To test larger numbers, use {@link BigInteger#isProbablePrime}.
997   *
998   * @throws IllegalArgumentException if {@code n} is negative
999   * @since 20.0
1000   */
1001  @GwtIncompatible // TODO
1002  @Beta
1003  public static boolean isPrime(long n) {
1004    if (n < 2) {
1005      checkNonNegative("n", n);
1006      return false;
1007    }
1008    if (n < 66) {
1009      // Encode all primes less than 66 into mask without 0 and 1.
1010      long mask =
1011          (1L << (2 - 2))
1012              | (1L << (3 - 2))
1013              | (1L << (5 - 2))
1014              | (1L << (7 - 2))
1015              | (1L << (11 - 2))
1016              | (1L << (13 - 2))
1017              | (1L << (17 - 2))
1018              | (1L << (19 - 2))
1019              | (1L << (23 - 2))
1020              | (1L << (29 - 2))
1021              | (1L << (31 - 2))
1022              | (1L << (37 - 2))
1023              | (1L << (41 - 2))
1024              | (1L << (43 - 2))
1025              | (1L << (47 - 2))
1026              | (1L << (53 - 2))
1027              | (1L << (59 - 2))
1028              | (1L << (61 - 2));
1029      // Look up n within the mask.
1030      return ((mask >> ((int) n - 2)) & 1) != 0;
1031    }
1032
1033    if ((SIEVE_30 & (1 << (n % 30))) != 0) {
1034      return false;
1035    }
1036    if (n % 7 == 0 || n % 11 == 0 || n % 13 == 0) {
1037      return false;
1038    }
1039    if (n < 17 * 17) {
1040      return true;
1041    }
1042
1043    for (long[] baseSet : millerRabinBaseSets) {
1044      if (n <= baseSet[0]) {
1045        for (int i = 1; i < baseSet.length; i++) {
1046          if (!MillerRabinTester.test(baseSet[i], n)) {
1047            return false;
1048          }
1049        }
1050        return true;
1051      }
1052    }
1053    throw new AssertionError();
1054  }
1055
1056  /*
1057   * If n <= millerRabinBases[i][0], then testing n against bases millerRabinBases[i][1..] suffices
1058   * to prove its primality. Values from miller-rabin.appspot.com.
1059   *
1060   * NOTE: We could get slightly better bases that would be treated as unsigned, but benchmarks
1061   * showed negligible performance improvements.
1062   */
1063  private static final long[][] millerRabinBaseSets = {
1064    {291830, 126401071349994536L},
1065    {885594168, 725270293939359937L, 3569819667048198375L},
1066    {273919523040L, 15, 7363882082L, 992620450144556L},
1067    {47636622961200L, 2, 2570940, 211991001, 3749873356L},
1068    {
1069      7999252175582850L,
1070      2,
1071      4130806001517L,
1072      149795463772692060L,
1073      186635894390467037L,
1074      3967304179347715805L
1075    },
1076    {
1077      585226005592931976L,
1078      2,
1079      123635709730000L,
1080      9233062284813009L,
1081      43835965440333360L,
1082      761179012939631437L,
1083      1263739024124850375L
1084    },
1085    {Long.MAX_VALUE, 2, 325, 9375, 28178, 450775, 9780504, 1795265022}
1086  };
1087
1088  private enum MillerRabinTester {
1089    /** Works for inputs ≤ FLOOR_SQRT_MAX_LONG. */
1090    SMALL {
1091      @Override
1092      long mulMod(long a, long b, long m) {
1093        /*
1094         * lowasser, 2015-Feb-12: Benchmarks suggest that changing this to UnsignedLongs.remainder
1095         * and increasing the threshold to 2^32 doesn't pay for itself, and adding another enum
1096         * constant hurts performance further -- I suspect because bimorphic implementation is a
1097         * sweet spot for the JVM.
1098         */
1099        return (a * b) % m;
1100      }
1101
1102      @Override
1103      long squareMod(long a, long m) {
1104        return (a * a) % m;
1105      }
1106    },
1107    /** Works for all nonnegative signed longs. */
1108    LARGE {
1109      /** Returns (a + b) mod m. Precondition: {@code 0 <= a}, {@code b < m < 2^63}. */
1110      private long plusMod(long a, long b, long m) {
1111        return (a >= m - b) ? (a + b - m) : (a + b);
1112      }
1113
1114      /** Returns (a * 2^32) mod m. a may be any unsigned long. */
1115      private long times2ToThe32Mod(long a, long m) {
1116        int remainingPowersOf2 = 32;
1117        do {
1118          int shift = Math.min(remainingPowersOf2, Long.numberOfLeadingZeros(a));
1119          // shift is either the number of powers of 2 left to multiply a by, or the biggest shift
1120          // possible while keeping a in an unsigned long.
1121          a = UnsignedLongs.remainder(a << shift, m);
1122          remainingPowersOf2 -= shift;
1123        } while (remainingPowersOf2 > 0);
1124        return a;
1125      }
1126
1127      @Override
1128      long mulMod(long a, long b, long m) {
1129        long aHi = a >>> 32; // < 2^31
1130        long bHi = b >>> 32; // < 2^31
1131        long aLo = a & 0xFFFFFFFFL; // < 2^32
1132        long bLo = b & 0xFFFFFFFFL; // < 2^32
1133
1134        /*
1135         * a * b == aHi * bHi * 2^64 + (aHi * bLo + aLo * bHi) * 2^32 + aLo * bLo.
1136         *       == (aHi * bHi * 2^32 + aHi * bLo + aLo * bHi) * 2^32 + aLo * bLo
1137         *
1138         * We carry out this computation in modular arithmetic. Since times2ToThe32Mod accepts any
1139         * unsigned long, we don't have to do a mod on every operation, only when intermediate
1140         * results can exceed 2^63.
1141         */
1142        long result = times2ToThe32Mod(aHi * bHi /* < 2^62 */, m); // < m < 2^63
1143        result += aHi * bLo; // aHi * bLo < 2^63, result < 2^64
1144        if (result < 0) {
1145          result = UnsignedLongs.remainder(result, m);
1146        }
1147        // result < 2^63 again
1148        result += aLo * bHi; // aLo * bHi < 2^63, result < 2^64
1149        result = times2ToThe32Mod(result, m); // result < m < 2^63
1150        return plusMod(result, UnsignedLongs.remainder(aLo * bLo /* < 2^64 */, m), m);
1151      }
1152
1153      @Override
1154      long squareMod(long a, long m) {
1155        long aHi = a >>> 32; // < 2^31
1156        long aLo = a & 0xFFFFFFFFL; // < 2^32
1157
1158        /*
1159         * a^2 == aHi^2 * 2^64 + aHi * aLo * 2^33 + aLo^2
1160         *     == (aHi^2 * 2^32 + aHi * aLo * 2) * 2^32 + aLo^2
1161         * We carry out this computation in modular arithmetic.  Since times2ToThe32Mod accepts any
1162         * unsigned long, we don't have to do a mod on every operation, only when intermediate
1163         * results can exceed 2^63.
1164         */
1165        long result = times2ToThe32Mod(aHi * aHi /* < 2^62 */, m); // < m < 2^63
1166        long hiLo = aHi * aLo * 2;
1167        if (hiLo < 0) {
1168          hiLo = UnsignedLongs.remainder(hiLo, m);
1169        }
1170        // hiLo < 2^63
1171        result += hiLo; // result < 2^64
1172        result = times2ToThe32Mod(result, m); // result < m < 2^63
1173        return plusMod(result, UnsignedLongs.remainder(aLo * aLo /* < 2^64 */, m), m);
1174      }
1175    };
1176
1177    static boolean test(long base, long n) {
1178      // Since base will be considered % n, it's okay if base > FLOOR_SQRT_MAX_LONG,
1179      // so long as n <= FLOOR_SQRT_MAX_LONG.
1180      return ((n <= FLOOR_SQRT_MAX_LONG) ? SMALL : LARGE).testWitness(base, n);
1181    }
1182
1183    /** Returns a * b mod m. */
1184    abstract long mulMod(long a, long b, long m);
1185
1186    /** Returns a^2 mod m. */
1187    abstract long squareMod(long a, long m);
1188
1189    /** Returns a^p mod m. */
1190    private long powMod(long a, long p, long m) {
1191      long res = 1;
1192      for (; p != 0; p >>= 1) {
1193        if ((p & 1) != 0) {
1194          res = mulMod(res, a, m);
1195        }
1196        a = squareMod(a, m);
1197      }
1198      return res;
1199    }
1200
1201    /** Returns true if n is a strong probable prime relative to the specified base. */
1202    private boolean testWitness(long base, long n) {
1203      int r = Long.numberOfTrailingZeros(n - 1);
1204      long d = (n - 1) >> r;
1205      base %= n;
1206      if (base == 0) {
1207        return true;
1208      }
1209      // Calculate a := base^d mod n.
1210      long a = powMod(base, d, n);
1211      // n passes this test if
1212      //    base^d = 1 (mod n)
1213      // or base^(2^j * d) = -1 (mod n) for some 0 <= j < r.
1214      if (a == 1) {
1215        return true;
1216      }
1217      int j = 0;
1218      while (a != n - 1) {
1219        if (++j == r) {
1220          return false;
1221        }
1222        a = squareMod(a, n);
1223      }
1224      return true;
1225    }
1226  }
1227
1228  /**
1229   * Returns {@code x}, rounded to a {@code double} with the specified rounding mode. If {@code x}
1230   * is precisely representable as a {@code double}, its {@code double} value will be returned;
1231   * otherwise, the rounding will choose between the two nearest representable values with {@code
1232   * mode}.
1233   *
1234   * <p>For the case of {@link RoundingMode#HALF_EVEN}, this implementation uses the IEEE 754
1235   * default rounding mode: if the two nearest representable values are equally near, the one with
1236   * the least significant bit zero is chosen. (In such cases, both of the nearest representable
1237   * values are even integers; this method returns the one that is a multiple of a greater power of
1238   * two.)
1239   *
1240   * @throws ArithmeticException if {@code mode} is {@link RoundingMode#UNNECESSARY} and {@code x}
1241   *     is not precisely representable as a {@code double}
1242   * @since 30.0
1243   */
1244  @SuppressWarnings("deprecation")
1245  @GwtIncompatible
1246  public static double roundToDouble(long x, RoundingMode mode) {
1247    // Logic adapted from ToDoubleRounder.
1248    double roundArbitrarily = (double) x;
1249    long roundArbitrarilyAsLong = (long) roundArbitrarily;
1250    int cmpXToRoundArbitrarily;
1251
1252    if (roundArbitrarilyAsLong == Long.MAX_VALUE) {
1253      /*
1254       * For most values, the conversion from roundArbitrarily to roundArbitrarilyAsLong is
1255       * lossless. In that case we can compare x to roundArbitrarily using Longs.compare(x,
1256       * roundArbitrarilyAsLong). The exception is for values where the conversion to double rounds
1257       * up to give roundArbitrarily equal to 2^63, so the conversion back to long overflows and
1258       * roundArbitrarilyAsLong is Long.MAX_VALUE. (This is the only way this condition can occur as
1259       * otherwise the conversion back to long pads with zero bits.) In this case we know that
1260       * roundArbitrarily > x. (This is important when x == Long.MAX_VALUE ==
1261       * roundArbitrarilyAsLong.)
1262       */
1263      cmpXToRoundArbitrarily = -1;
1264    } else {
1265      cmpXToRoundArbitrarily = Longs.compare(x, roundArbitrarilyAsLong);
1266    }
1267
1268    switch (mode) {
1269      case UNNECESSARY:
1270        checkRoundingUnnecessary(cmpXToRoundArbitrarily == 0);
1271        return roundArbitrarily;
1272      case FLOOR:
1273        return (cmpXToRoundArbitrarily >= 0)
1274            ? roundArbitrarily
1275            : DoubleUtils.nextDown(roundArbitrarily);
1276      case CEILING:
1277        return (cmpXToRoundArbitrarily <= 0) ? roundArbitrarily : Math.nextUp(roundArbitrarily);
1278      case DOWN:
1279        if (x >= 0) {
1280          return (cmpXToRoundArbitrarily >= 0)
1281              ? roundArbitrarily
1282              : DoubleUtils.nextDown(roundArbitrarily);
1283        } else {
1284          return (cmpXToRoundArbitrarily <= 0) ? roundArbitrarily : Math.nextUp(roundArbitrarily);
1285        }
1286      case UP:
1287        if (x >= 0) {
1288          return (cmpXToRoundArbitrarily <= 0) ? roundArbitrarily : Math.nextUp(roundArbitrarily);
1289        } else {
1290          return (cmpXToRoundArbitrarily >= 0)
1291              ? roundArbitrarily
1292              : DoubleUtils.nextDown(roundArbitrarily);
1293        }
1294      case HALF_DOWN:
1295      case HALF_UP:
1296      case HALF_EVEN:
1297        {
1298          long roundFloor;
1299          double roundFloorAsDouble;
1300          long roundCeiling;
1301          double roundCeilingAsDouble;
1302
1303          if (cmpXToRoundArbitrarily >= 0) {
1304            roundFloorAsDouble = roundArbitrarily;
1305            roundFloor = roundArbitrarilyAsLong;
1306            roundCeilingAsDouble = Math.nextUp(roundArbitrarily);
1307            roundCeiling = (long) Math.ceil(roundCeilingAsDouble);
1308          } else {
1309            roundCeilingAsDouble = roundArbitrarily;
1310            roundCeiling = roundArbitrarilyAsLong;
1311            roundFloorAsDouble = DoubleUtils.nextDown(roundArbitrarily);
1312            roundFloor = (long) Math.floor(roundFloorAsDouble);
1313          }
1314
1315          long deltaToFloor = x - roundFloor;
1316          long deltaToCeiling = roundCeiling - x;
1317
1318          if (roundCeiling == Long.MAX_VALUE) {
1319            // correct for Long.MAX_VALUE as discussed above: roundCeilingAsDouble must be 2^63, but
1320            // roundCeiling is 2^63-1.
1321            deltaToCeiling++;
1322          }
1323
1324          int diff = Longs.compare(deltaToFloor, deltaToCeiling);
1325          if (diff < 0) { // closer to floor
1326            return roundFloorAsDouble;
1327          } else if (diff > 0) { // closer to ceiling
1328            return roundCeilingAsDouble;
1329          }
1330          // halfway between the representable values; do the half-whatever logic
1331          switch (mode) {
1332            case HALF_EVEN:
1333              return ((DoubleUtils.getSignificand(roundFloorAsDouble) & 1L) == 0)
1334                  ? roundFloorAsDouble
1335                  : roundCeilingAsDouble;
1336            case HALF_DOWN:
1337              return (x >= 0) ? roundFloorAsDouble : roundCeilingAsDouble;
1338            case HALF_UP:
1339              return (x >= 0) ? roundCeilingAsDouble : roundFloorAsDouble;
1340            default:
1341              throw new AssertionError("impossible");
1342          }
1343        }
1344    }
1345    throw new AssertionError("impossible");
1346  }
1347
1348  private LongMath() {}
1349}