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  @GwtIncompatible // TODO
547  public static long checkedAdd(long a, long b) {
548    long result = a + b;
549    checkNoOverflow((a ^ b) < 0 | (a ^ result) >= 0, "checkedAdd", a, b);
550    return result;
551  }
552
553  /**
554   * Returns the difference of {@code a} and {@code b}, provided it does not overflow.
555   *
556   * @throws ArithmeticException if {@code a - b} overflows in signed {@code long} arithmetic
557   */
558  @GwtIncompatible // TODO
559  public static long checkedSubtract(long a, long b) {
560    long result = a - b;
561    checkNoOverflow((a ^ b) >= 0 | (a ^ result) >= 0, "checkedSubtract", a, b);
562    return result;
563  }
564
565  /**
566   * Returns the product of {@code a} and {@code b}, provided it does not overflow.
567   *
568   * @throws ArithmeticException if {@code a * b} overflows in signed {@code long} arithmetic
569   */
570  public static long checkedMultiply(long a, long b) {
571    // Hacker's Delight, Section 2-12
572    int leadingZeros =
573        Long.numberOfLeadingZeros(a)
574            + Long.numberOfLeadingZeros(~a)
575            + Long.numberOfLeadingZeros(b)
576            + Long.numberOfLeadingZeros(~b);
577    /*
578     * If leadingZeros > Long.SIZE + 1 it's definitely fine, if it's < Long.SIZE it's definitely
579     * bad. We do the leadingZeros check to avoid the division below if at all possible.
580     *
581     * Otherwise, if b == Long.MIN_VALUE, then the only allowed values of a are 0 and 1. We take
582     * care of all a < 0 with their own check, because in particular, the case a == -1 will
583     * incorrectly pass the division check below.
584     *
585     * In all other cases, we check that either a is 0 or the result is consistent with division.
586     */
587    if (leadingZeros > Long.SIZE + 1) {
588      return a * b;
589    }
590    checkNoOverflow(leadingZeros >= Long.SIZE, "checkedMultiply", a, b);
591    checkNoOverflow(a >= 0 | b != Long.MIN_VALUE, "checkedMultiply", a, b);
592    long result = a * b;
593    checkNoOverflow(a == 0 || result / a == b, "checkedMultiply", a, b);
594    return result;
595  }
596
597  /**
598   * Returns the {@code b} to the {@code k}th power, provided it does not overflow.
599   *
600   * @throws ArithmeticException if {@code b} to the {@code k}th power overflows in signed {@code
601   *     long} arithmetic
602   */
603  @GwtIncompatible // TODO
604  public static long checkedPow(long b, int k) {
605    checkNonNegative("exponent", k);
606    if (b >= -2 & b <= 2) {
607      switch ((int) b) {
608        case 0:
609          return (k == 0) ? 1 : 0;
610        case 1:
611          return 1;
612        case (-1):
613          return ((k & 1) == 0) ? 1 : -1;
614        case 2:
615          checkNoOverflow(k < Long.SIZE - 1, "checkedPow", b, k);
616          return 1L << k;
617        case (-2):
618          checkNoOverflow(k < Long.SIZE, "checkedPow", b, k);
619          return ((k & 1) == 0) ? (1L << k) : (-1L << k);
620        default:
621          throw new AssertionError();
622      }
623    }
624    long accum = 1;
625    while (true) {
626      switch (k) {
627        case 0:
628          return accum;
629        case 1:
630          return checkedMultiply(accum, b);
631        default:
632          if ((k & 1) != 0) {
633            accum = checkedMultiply(accum, b);
634          }
635          k >>= 1;
636          if (k > 0) {
637            checkNoOverflow(
638                -FLOOR_SQRT_MAX_LONG <= b && b <= FLOOR_SQRT_MAX_LONG, "checkedPow", b, k);
639            b *= b;
640          }
641      }
642    }
643  }
644
645  /**
646   * Returns the sum of {@code a} and {@code b} unless it would overflow or underflow in which case
647   * {@code Long.MAX_VALUE} or {@code Long.MIN_VALUE} is returned, respectively.
648   *
649   * @since 20.0
650   */
651  @Beta
652  public static long saturatedAdd(long a, long b) {
653    long naiveSum = a + b;
654    if ((a ^ b) < 0 | (a ^ naiveSum) >= 0) {
655      // If a and b have different signs or a has the same sign as the result then there was no
656      // overflow, return.
657      return naiveSum;
658    }
659    // we did over/under flow, if the sign is negative we should return MAX otherwise MIN
660    return Long.MAX_VALUE + ((naiveSum >>> (Long.SIZE - 1)) ^ 1);
661  }
662
663  /**
664   * Returns the difference of {@code a} and {@code b} unless it would overflow or underflow in
665   * which case {@code Long.MAX_VALUE} or {@code Long.MIN_VALUE} is returned, respectively.
666   *
667   * @since 20.0
668   */
669  @Beta
670  public static long saturatedSubtract(long a, long b) {
671    long naiveDifference = a - b;
672    if ((a ^ b) >= 0 | (a ^ naiveDifference) >= 0) {
673      // If a and b have the same signs or a has the same sign as the result then there was no
674      // overflow, return.
675      return naiveDifference;
676    }
677    // we did over/under flow
678    return Long.MAX_VALUE + ((naiveDifference >>> (Long.SIZE - 1)) ^ 1);
679  }
680
681  /**
682   * Returns the product of {@code a} and {@code b} unless it would overflow or underflow in which
683   * case {@code Long.MAX_VALUE} or {@code Long.MIN_VALUE} is returned, respectively.
684   *
685   * @since 20.0
686   */
687  @Beta
688  public static long saturatedMultiply(long a, long b) {
689    // see checkedMultiply for explanation
690    int leadingZeros =
691        Long.numberOfLeadingZeros(a)
692            + Long.numberOfLeadingZeros(~a)
693            + Long.numberOfLeadingZeros(b)
694            + Long.numberOfLeadingZeros(~b);
695    if (leadingZeros > Long.SIZE + 1) {
696      return a * b;
697    }
698    // the return value if we will overflow (which we calculate by overflowing a long :) )
699    long limit = Long.MAX_VALUE + ((a ^ b) >>> (Long.SIZE - 1));
700    if (leadingZeros < Long.SIZE | (a < 0 & b == Long.MIN_VALUE)) {
701      // overflow
702      return limit;
703    }
704    long result = a * b;
705    if (a == 0 || result / a == b) {
706      return result;
707    }
708    return limit;
709  }
710
711  /**
712   * Returns the {@code b} to the {@code k}th power, unless it would overflow or underflow in which
713   * case {@code Long.MAX_VALUE} or {@code Long.MIN_VALUE} is returned, respectively.
714   *
715   * @since 20.0
716   */
717  @Beta
718  public static long saturatedPow(long b, int k) {
719    checkNonNegative("exponent", k);
720    if (b >= -2 & b <= 2) {
721      switch ((int) b) {
722        case 0:
723          return (k == 0) ? 1 : 0;
724        case 1:
725          return 1;
726        case (-1):
727          return ((k & 1) == 0) ? 1 : -1;
728        case 2:
729          if (k >= Long.SIZE - 1) {
730            return Long.MAX_VALUE;
731          }
732          return 1L << k;
733        case (-2):
734          if (k >= Long.SIZE) {
735            return Long.MAX_VALUE + (k & 1);
736          }
737          return ((k & 1) == 0) ? (1L << k) : (-1L << k);
738        default:
739          throw new AssertionError();
740      }
741    }
742    long accum = 1;
743    // if b is negative and k is odd then the limit is MIN otherwise the limit is MAX
744    long limit = Long.MAX_VALUE + ((b >>> Long.SIZE - 1) & (k & 1));
745    while (true) {
746      switch (k) {
747        case 0:
748          return accum;
749        case 1:
750          return saturatedMultiply(accum, b);
751        default:
752          if ((k & 1) != 0) {
753            accum = saturatedMultiply(accum, b);
754          }
755          k >>= 1;
756          if (k > 0) {
757            if (-FLOOR_SQRT_MAX_LONG > b | b > FLOOR_SQRT_MAX_LONG) {
758              return limit;
759            }
760            b *= b;
761          }
762      }
763    }
764  }
765
766  @VisibleForTesting static final long FLOOR_SQRT_MAX_LONG = 3037000499L;
767
768  /**
769   * Returns {@code n!}, that is, the product of the first {@code n} positive integers, {@code 1} if
770   * {@code n == 0}, or {@link Long#MAX_VALUE} if the result does not fit in a {@code long}.
771   *
772   * @throws IllegalArgumentException if {@code n < 0}
773   */
774  @GwtIncompatible // TODO
775  public static long factorial(int n) {
776    checkNonNegative("n", n);
777    return (n < factorials.length) ? factorials[n] : Long.MAX_VALUE;
778  }
779
780  static final long[] factorials = {
781    1L,
782    1L,
783    1L * 2,
784    1L * 2 * 3,
785    1L * 2 * 3 * 4,
786    1L * 2 * 3 * 4 * 5,
787    1L * 2 * 3 * 4 * 5 * 6,
788    1L * 2 * 3 * 4 * 5 * 6 * 7,
789    1L * 2 * 3 * 4 * 5 * 6 * 7 * 8,
790    1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9,
791    1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10,
792    1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11,
793    1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12,
794    1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13,
795    1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14,
796    1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15,
797    1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16,
798    1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17,
799    1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17 * 18,
800    1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17 * 18 * 19,
801    1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17 * 18 * 19 * 20
802  };
803
804  /**
805   * Returns {@code n} choose {@code k}, also known as the binomial coefficient of {@code n} and
806   * {@code k}, or {@link Long#MAX_VALUE} if the result does not fit in a {@code long}.
807   *
808   * @throws IllegalArgumentException if {@code n < 0}, {@code k < 0}, or {@code k > n}
809   */
810  public static long binomial(int n, int k) {
811    checkNonNegative("n", n);
812    checkNonNegative("k", k);
813    checkArgument(k <= n, "k (%s) > n (%s)", k, n);
814    if (k > (n >> 1)) {
815      k = n - k;
816    }
817    switch (k) {
818      case 0:
819        return 1;
820      case 1:
821        return n;
822      default:
823        if (n < factorials.length) {
824          return factorials[n] / (factorials[k] * factorials[n - k]);
825        } else if (k >= biggestBinomials.length || n > biggestBinomials[k]) {
826          return Long.MAX_VALUE;
827        } else if (k < biggestSimpleBinomials.length && n <= biggestSimpleBinomials[k]) {
828          // guaranteed not to overflow
829          long result = n--;
830          for (int i = 2; i <= k; n--, i++) {
831            result *= n;
832            result /= i;
833          }
834          return result;
835        } else {
836          int nBits = LongMath.log2(n, RoundingMode.CEILING);
837
838          long result = 1;
839          long numerator = n--;
840          long denominator = 1;
841
842          int numeratorBits = nBits;
843          // This is an upper bound on log2(numerator, ceiling).
844
845          /*
846           * We want to do this in long math for speed, but want to avoid overflow. We adapt the
847           * technique previously used by BigIntegerMath: maintain separate numerator and
848           * denominator accumulators, multiplying the fraction into result when near overflow.
849           */
850          for (int i = 2; i <= k; i++, n--) {
851            if (numeratorBits + nBits < Long.SIZE - 1) {
852              // It's definitely safe to multiply into numerator and denominator.
853              numerator *= n;
854              denominator *= i;
855              numeratorBits += nBits;
856            } else {
857              // It might not be safe to multiply into numerator and denominator,
858              // so multiply (numerator / denominator) into result.
859              result = multiplyFraction(result, numerator, denominator);
860              numerator = n;
861              denominator = i;
862              numeratorBits = nBits;
863            }
864          }
865          return multiplyFraction(result, numerator, denominator);
866        }
867    }
868  }
869
870  /** Returns (x * numerator / denominator), which is assumed to come out to an integral value. */
871  static long multiplyFraction(long x, long numerator, long denominator) {
872    if (x == 1) {
873      return numerator / denominator;
874    }
875    long commonDivisor = gcd(x, denominator);
876    x /= commonDivisor;
877    denominator /= commonDivisor;
878    // We know gcd(x, denominator) = 1, and x * numerator / denominator is exact,
879    // so denominator must be a divisor of numerator.
880    return x * (numerator / denominator);
881  }
882
883  /*
884   * binomial(biggestBinomials[k], k) fits in a long, but not binomial(biggestBinomials[k] + 1, k).
885   */
886  static final int[] biggestBinomials = {
887    Integer.MAX_VALUE,
888    Integer.MAX_VALUE,
889    Integer.MAX_VALUE,
890    3810779,
891    121977,
892    16175,
893    4337,
894    1733,
895    887,
896    534,
897    361,
898    265,
899    206,
900    169,
901    143,
902    125,
903    111,
904    101,
905    94,
906    88,
907    83,
908    79,
909    76,
910    74,
911    72,
912    70,
913    69,
914    68,
915    67,
916    67,
917    66,
918    66,
919    66,
920    66
921  };
922
923  /*
924   * binomial(biggestSimpleBinomials[k], k) doesn't need to use the slower GCD-based impl, but
925   * binomial(biggestSimpleBinomials[k] + 1, k) does.
926   */
927  @VisibleForTesting
928  static final int[] biggestSimpleBinomials = {
929    Integer.MAX_VALUE,
930    Integer.MAX_VALUE,
931    Integer.MAX_VALUE,
932    2642246,
933    86251,
934    11724,
935    3218,
936    1313,
937    684,
938    419,
939    287,
940    214,
941    169,
942    139,
943    119,
944    105,
945    95,
946    87,
947    81,
948    76,
949    73,
950    70,
951    68,
952    66,
953    64,
954    63,
955    62,
956    62,
957    61,
958    61,
959    61
960  };
961  // These values were generated by using checkedMultiply to see when the simple multiply/divide
962  // algorithm would lead to an overflow.
963
964  static boolean fitsInInt(long x) {
965    return (int) x == x;
966  }
967
968  /**
969   * Returns the arithmetic mean of {@code x} and {@code y}, rounded toward negative infinity. This
970   * method is resilient to overflow.
971   *
972   * @since 14.0
973   */
974  public static long mean(long x, long y) {
975    // Efficient method for computing the arithmetic mean.
976    // The alternative (x + y) / 2 fails for large values.
977    // The alternative (x + y) >>> 1 fails for negative values.
978    return (x & y) + ((x ^ y) >> 1);
979  }
980
981  /*
982   * This bitmask is used as an optimization for cheaply testing for divisiblity by 2, 3, or 5.
983   * Each bit is set to 1 for all remainders that indicate divisibility by 2, 3, or 5, so
984   * 1, 7, 11, 13, 17, 19, 23, 29 are set to 0. 30 and up don't matter because they won't be hit.
985   */
986  private static final int SIEVE_30 =
987      ~((1 << 1) | (1 << 7) | (1 << 11) | (1 << 13) | (1 << 17) | (1 << 19) | (1 << 23)
988          | (1 << 29));
989
990  /**
991   * Returns {@code true} if {@code n} is a <a
992   * href="http://mathworld.wolfram.com/PrimeNumber.html">prime number</a>: an integer <i>greater
993   * than one</i> that cannot be factored into a product of <i>smaller</i> positive integers.
994   * Returns {@code false} if {@code n} is zero, one, or a composite number (one which <i>can</i> be
995   * factored into smaller positive integers).
996   *
997   * <p>To test larger numbers, use {@link BigInteger#isProbablePrime}.
998   *
999   * @throws IllegalArgumentException if {@code n} is negative
1000   * @since 20.0
1001   */
1002  @GwtIncompatible // TODO
1003  @Beta
1004  public static boolean isPrime(long n) {
1005    if (n < 2) {
1006      checkNonNegative("n", n);
1007      return false;
1008    }
1009    if (n < 66) {
1010      // Encode all primes less than 66 into mask without 0 and 1.
1011      long mask =
1012          (1L << (2 - 2))
1013              | (1L << (3 - 2))
1014              | (1L << (5 - 2))
1015              | (1L << (7 - 2))
1016              | (1L << (11 - 2))
1017              | (1L << (13 - 2))
1018              | (1L << (17 - 2))
1019              | (1L << (19 - 2))
1020              | (1L << (23 - 2))
1021              | (1L << (29 - 2))
1022              | (1L << (31 - 2))
1023              | (1L << (37 - 2))
1024              | (1L << (41 - 2))
1025              | (1L << (43 - 2))
1026              | (1L << (47 - 2))
1027              | (1L << (53 - 2))
1028              | (1L << (59 - 2))
1029              | (1L << (61 - 2));
1030      // Look up n within the mask.
1031      return ((mask >> ((int) n - 2)) & 1) != 0;
1032    }
1033
1034    if ((SIEVE_30 & (1 << (n % 30))) != 0) {
1035      return false;
1036    }
1037    if (n % 7 == 0 || n % 11 == 0 || n % 13 == 0) {
1038      return false;
1039    }
1040    if (n < 17 * 17) {
1041      return true;
1042    }
1043
1044    for (long[] baseSet : millerRabinBaseSets) {
1045      if (n <= baseSet[0]) {
1046        for (int i = 1; i < baseSet.length; i++) {
1047          if (!MillerRabinTester.test(baseSet[i], n)) {
1048            return false;
1049          }
1050        }
1051        return true;
1052      }
1053    }
1054    throw new AssertionError();
1055  }
1056
1057  /*
1058   * If n <= millerRabinBases[i][0], then testing n against bases millerRabinBases[i][1..] suffices
1059   * to prove its primality. Values from miller-rabin.appspot.com.
1060   *
1061   * NOTE: We could get slightly better bases that would be treated as unsigned, but benchmarks
1062   * showed negligible performance improvements.
1063   */
1064  private static final long[][] millerRabinBaseSets = {
1065    {291830, 126401071349994536L},
1066    {885594168, 725270293939359937L, 3569819667048198375L},
1067    {273919523040L, 15, 7363882082L, 992620450144556L},
1068    {47636622961200L, 2, 2570940, 211991001, 3749873356L},
1069    {
1070      7999252175582850L,
1071      2,
1072      4130806001517L,
1073      149795463772692060L,
1074      186635894390467037L,
1075      3967304179347715805L
1076    },
1077    {
1078      585226005592931976L,
1079      2,
1080      123635709730000L,
1081      9233062284813009L,
1082      43835965440333360L,
1083      761179012939631437L,
1084      1263739024124850375L
1085    },
1086    {Long.MAX_VALUE, 2, 325, 9375, 28178, 450775, 9780504, 1795265022}
1087  };
1088
1089  private enum MillerRabinTester {
1090    /** Works for inputs ≤ FLOOR_SQRT_MAX_LONG. */
1091    SMALL {
1092      @Override
1093      long mulMod(long a, long b, long m) {
1094        /*
1095         * lowasser, 2015-Feb-12: Benchmarks suggest that changing this to UnsignedLongs.remainder
1096         * and increasing the threshold to 2^32 doesn't pay for itself, and adding another enum
1097         * constant hurts performance further -- I suspect because bimorphic implementation is a
1098         * sweet spot for the JVM.
1099         */
1100        return (a * b) % m;
1101      }
1102
1103      @Override
1104      long squareMod(long a, long m) {
1105        return (a * a) % m;
1106      }
1107    },
1108    /** Works for all nonnegative signed longs. */
1109    LARGE {
1110      /** Returns (a + b) mod m. Precondition: {@code 0 <= a}, {@code b < m < 2^63}. */
1111      private long plusMod(long a, long b, long m) {
1112        return (a >= m - b) ? (a + b - m) : (a + b);
1113      }
1114
1115      /** Returns (a * 2^32) mod m. a may be any unsigned long. */
1116      private long times2ToThe32Mod(long a, long m) {
1117        int remainingPowersOf2 = 32;
1118        do {
1119          int shift = Math.min(remainingPowersOf2, Long.numberOfLeadingZeros(a));
1120          // shift is either the number of powers of 2 left to multiply a by, or the biggest shift
1121          // possible while keeping a in an unsigned long.
1122          a = UnsignedLongs.remainder(a << shift, m);
1123          remainingPowersOf2 -= shift;
1124        } while (remainingPowersOf2 > 0);
1125        return a;
1126      }
1127
1128      @Override
1129      long mulMod(long a, long b, long m) {
1130        long aHi = a >>> 32; // < 2^31
1131        long bHi = b >>> 32; // < 2^31
1132        long aLo = a & 0xFFFFFFFFL; // < 2^32
1133        long bLo = b & 0xFFFFFFFFL; // < 2^32
1134
1135        /*
1136         * a * b == aHi * bHi * 2^64 + (aHi * bLo + aLo * bHi) * 2^32 + aLo * bLo.
1137         *       == (aHi * bHi * 2^32 + aHi * bLo + aLo * bHi) * 2^32 + aLo * bLo
1138         *
1139         * We carry out this computation in modular arithmetic. Since times2ToThe32Mod accepts any
1140         * unsigned long, we don't have to do a mod on every operation, only when intermediate
1141         * results can exceed 2^63.
1142         */
1143        long result = times2ToThe32Mod(aHi * bHi /* < 2^62 */, m); // < m < 2^63
1144        result += aHi * bLo; // aHi * bLo < 2^63, result < 2^64
1145        if (result < 0) {
1146          result = UnsignedLongs.remainder(result, m);
1147        }
1148        // result < 2^63 again
1149        result += aLo * bHi; // aLo * bHi < 2^63, result < 2^64
1150        result = times2ToThe32Mod(result, m); // result < m < 2^63
1151        return plusMod(result, UnsignedLongs.remainder(aLo * bLo /* < 2^64 */, m), m);
1152      }
1153
1154      @Override
1155      long squareMod(long a, long m) {
1156        long aHi = a >>> 32; // < 2^31
1157        long aLo = a & 0xFFFFFFFFL; // < 2^32
1158
1159        /*
1160         * a^2 == aHi^2 * 2^64 + aHi * aLo * 2^33 + aLo^2
1161         *     == (aHi^2 * 2^32 + aHi * aLo * 2) * 2^32 + aLo^2
1162         * We carry out this computation in modular arithmetic.  Since times2ToThe32Mod accepts any
1163         * unsigned long, we don't have to do a mod on every operation, only when intermediate
1164         * results can exceed 2^63.
1165         */
1166        long result = times2ToThe32Mod(aHi * aHi /* < 2^62 */, m); // < m < 2^63
1167        long hiLo = aHi * aLo * 2;
1168        if (hiLo < 0) {
1169          hiLo = UnsignedLongs.remainder(hiLo, m);
1170        }
1171        // hiLo < 2^63
1172        result += hiLo; // result < 2^64
1173        result = times2ToThe32Mod(result, m); // result < m < 2^63
1174        return plusMod(result, UnsignedLongs.remainder(aLo * aLo /* < 2^64 */, m), m);
1175      }
1176    };
1177
1178    static boolean test(long base, long n) {
1179      // Since base will be considered % n, it's okay if base > FLOOR_SQRT_MAX_LONG,
1180      // so long as n <= FLOOR_SQRT_MAX_LONG.
1181      return ((n <= FLOOR_SQRT_MAX_LONG) ? SMALL : LARGE).testWitness(base, n);
1182    }
1183
1184    /** Returns a * b mod m. */
1185    abstract long mulMod(long a, long b, long m);
1186
1187    /** Returns a^2 mod m. */
1188    abstract long squareMod(long a, long m);
1189
1190    /** Returns a^p mod m. */
1191    private long powMod(long a, long p, long m) {
1192      long res = 1;
1193      for (; p != 0; p >>= 1) {
1194        if ((p & 1) != 0) {
1195          res = mulMod(res, a, m);
1196        }
1197        a = squareMod(a, m);
1198      }
1199      return res;
1200    }
1201
1202    /** Returns true if n is a strong probable prime relative to the specified base. */
1203    private boolean testWitness(long base, long n) {
1204      int r = Long.numberOfTrailingZeros(n - 1);
1205      long d = (n - 1) >> r;
1206      base %= n;
1207      if (base == 0) {
1208        return true;
1209      }
1210      // Calculate a := base^d mod n.
1211      long a = powMod(base, d, n);
1212      // n passes this test if
1213      //    base^d = 1 (mod n)
1214      // or base^(2^j * d) = -1 (mod n) for some 0 <= j < r.
1215      if (a == 1) {
1216        return true;
1217      }
1218      int j = 0;
1219      while (a != n - 1) {
1220        if (++j == r) {
1221          return false;
1222        }
1223        a = squareMod(a, n);
1224      }
1225      return true;
1226    }
1227  }
1228
1229  /**
1230   * Returns {@code x}, rounded to a {@code double} with the specified rounding mode. If {@code x}
1231   * is precisely representable as a {@code double}, its {@code double} value will be returned;
1232   * otherwise, the rounding will choose between the two nearest representable values with {@code
1233   * mode}.
1234   *
1235   * <p>For the case of {@link RoundingMode#HALF_EVEN}, this implementation uses the IEEE 754
1236   * default rounding mode: if the two nearest representable values are equally near, the one with
1237   * the least significant bit zero is chosen. (In such cases, both of the nearest representable
1238   * values are even integers; this method returns the one that is a multiple of a greater power of
1239   * two.)
1240   *
1241   * @throws ArithmeticException if {@code mode} is {@link RoundingMode#UNNECESSARY} and {@code x}
1242   *     is not precisely representable as a {@code double}
1243   * @since 30.0
1244   */
1245  @SuppressWarnings("deprecation")
1246  @GwtIncompatible
1247  public static double roundToDouble(long x, RoundingMode mode) {
1248    // Logic adapted from ToDoubleRounder.
1249    double roundArbitrarily = (double) x;
1250    long roundArbitrarilyAsLong = (long) roundArbitrarily;
1251    int cmpXToRoundArbitrarily;
1252
1253    if (roundArbitrarilyAsLong == Long.MAX_VALUE) {
1254      /*
1255       * For most values, the conversion from roundArbitrarily to roundArbitrarilyAsLong is
1256       * lossless. In that case we can compare x to roundArbitrarily using Longs.compare(x,
1257       * roundArbitrarilyAsLong). The exception is for values where the conversion to double rounds
1258       * up to give roundArbitrarily equal to 2^63, so the conversion back to long overflows and
1259       * roundArbitrarilyAsLong is Long.MAX_VALUE. (This is the only way this condition can occur as
1260       * otherwise the conversion back to long pads with zero bits.) In this case we know that
1261       * roundArbitrarily > x. (This is important when x == Long.MAX_VALUE ==
1262       * roundArbitrarilyAsLong.)
1263       */
1264      cmpXToRoundArbitrarily = -1;
1265    } else {
1266      cmpXToRoundArbitrarily = Longs.compare(x, roundArbitrarilyAsLong);
1267    }
1268
1269    switch (mode) {
1270      case UNNECESSARY:
1271        checkRoundingUnnecessary(cmpXToRoundArbitrarily == 0);
1272        return roundArbitrarily;
1273      case FLOOR:
1274        return (cmpXToRoundArbitrarily >= 0)
1275            ? roundArbitrarily
1276            : DoubleUtils.nextDown(roundArbitrarily);
1277      case CEILING:
1278        return (cmpXToRoundArbitrarily <= 0) ? roundArbitrarily : Math.nextUp(roundArbitrarily);
1279      case DOWN:
1280        if (x >= 0) {
1281          return (cmpXToRoundArbitrarily >= 0)
1282              ? roundArbitrarily
1283              : DoubleUtils.nextDown(roundArbitrarily);
1284        } else {
1285          return (cmpXToRoundArbitrarily <= 0) ? roundArbitrarily : Math.nextUp(roundArbitrarily);
1286        }
1287      case UP:
1288        if (x >= 0) {
1289          return (cmpXToRoundArbitrarily <= 0) ? roundArbitrarily : Math.nextUp(roundArbitrarily);
1290        } else {
1291          return (cmpXToRoundArbitrarily >= 0)
1292              ? roundArbitrarily
1293              : DoubleUtils.nextDown(roundArbitrarily);
1294        }
1295      case HALF_DOWN:
1296      case HALF_UP:
1297      case HALF_EVEN:
1298        {
1299          long roundFloor;
1300          double roundFloorAsDouble;
1301          long roundCeiling;
1302          double roundCeilingAsDouble;
1303
1304          if (cmpXToRoundArbitrarily >= 0) {
1305            roundFloorAsDouble = roundArbitrarily;
1306            roundFloor = roundArbitrarilyAsLong;
1307            roundCeilingAsDouble = Math.nextUp(roundArbitrarily);
1308            roundCeiling = (long) Math.ceil(roundCeilingAsDouble);
1309          } else {
1310            roundCeilingAsDouble = roundArbitrarily;
1311            roundCeiling = roundArbitrarilyAsLong;
1312            roundFloorAsDouble = DoubleUtils.nextDown(roundArbitrarily);
1313            roundFloor = (long) Math.floor(roundFloorAsDouble);
1314          }
1315
1316          long deltaToFloor = x - roundFloor;
1317          long deltaToCeiling = roundCeiling - x;
1318
1319          if (roundCeiling == Long.MAX_VALUE) {
1320            // correct for Long.MAX_VALUE as discussed above: roundCeilingAsDouble must be 2^63, but
1321            // roundCeiling is 2^63-1.
1322            deltaToCeiling++;
1323          }
1324
1325          int diff = Longs.compare(deltaToFloor, deltaToCeiling);
1326          if (diff < 0) { // closer to floor
1327            return roundFloorAsDouble;
1328          } else if (diff > 0) { // closer to ceiling
1329            return roundCeilingAsDouble;
1330          }
1331          // halfway between the representable values; do the half-whatever logic
1332          switch (mode) {
1333            case HALF_EVEN:
1334              return ((DoubleUtils.getSignificand(roundFloorAsDouble) & 1L) == 0)
1335                  ? roundFloorAsDouble
1336                  : roundCeilingAsDouble;
1337            case HALF_DOWN:
1338              return (x >= 0) ? roundFloorAsDouble : roundCeilingAsDouble;
1339            case HALF_UP:
1340              return (x >= 0) ? roundCeilingAsDouble : roundFloorAsDouble;
1341            default:
1342              throw new AssertionError("impossible");
1343          }
1344        }
1345    }
1346    throw new AssertionError("impossible");
1347  }
1348
1349  private LongMath() {}
1350}