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.GwtCompatible;
029import com.google.common.annotations.GwtIncompatible;
030import com.google.common.annotations.VisibleForTesting;
031import com.google.common.primitives.UnsignedLongs;
032import java.math.BigInteger;
033import java.math.RoundingMode;
034
035/**
036 * A class for arithmetic on values of type {@code long}. Where possible, methods are defined and
037 * named analogously to their {@code BigInteger} counterparts.
038 *
039 * <p>The implementations of many methods in this class are based on material from Henry S. Warren,
040 * Jr.'s <i>Hacker's Delight</i>, (Addison Wesley, 2002).
041 *
042 * <p>Similar functionality for {@code int} and for {@link BigInteger} can be found in {@link
043 * IntMath} and {@link BigIntegerMath} respectively. For other common operations on {@code long}
044 * values, see {@link com.google.common.primitives.Longs}.
045 *
046 * @author Louis Wasserman
047 * @since 11.0
048 */
049@GwtCompatible(emulated = true)
050public final class LongMath {
051  @VisibleForTesting static final long MAX_SIGNED_POWER_OF_TWO = 1L << (Long.SIZE - 2);
052
053  /**
054   * Returns the smallest power of two greater than or equal to {@code x}. This is equivalent to
055   * {@code checkedPow(2, log2(x, CEILING))}.
056   *
057   * @throws IllegalArgumentException if {@code x <= 0}
058   * @throws ArithmeticException of the next-higher power of two is not representable as a {@code
059   *     long}, i.e. when {@code x > 2^62}
060   * @since 20.0
061   */
062  public static long ceilingPowerOfTwo(long x) {
063    checkPositive("x", x);
064    if (x > MAX_SIGNED_POWER_OF_TWO) {
065      throw new ArithmeticException("ceilingPowerOfTwo(" + x + ") is not representable as a long");
066    }
067    return 1L << -Long.numberOfLeadingZeros(x - 1);
068  }
069
070  /**
071   * Returns the largest power of two less than or equal to {@code x}. This is equivalent to {@code
072   * checkedPow(2, log2(x, FLOOR))}.
073   *
074   * @throws IllegalArgumentException if {@code x <= 0}
075   * @since 20.0
076   */
077  public static long floorPowerOfTwo(long x) {
078    checkPositive("x", x);
079
080    // Long.highestOneBit was buggy on GWT.  We've fixed it, but I'm not certain when the fix will
081    // be released.
082    return 1L << ((Long.SIZE - 1) - Long.numberOfLeadingZeros(x));
083  }
084
085  /**
086   * Returns {@code true} if {@code x} represents a power of two.
087   *
088   * <p>This differs from {@code Long.bitCount(x) == 1}, because {@code
089   * Long.bitCount(Long.MIN_VALUE) == 1}, but {@link Long#MIN_VALUE} is not a power of two.
090   */
091  // Whenever both tests are cheap and functional, it's faster to use &, | instead of &&, ||
092  @SuppressWarnings("ShortCircuitBoolean")
093  public static boolean isPowerOfTwo(long x) {
094    return x > 0 & (x & (x - 1)) == 0;
095  }
096
097  /**
098   * Returns 1 if {@code x < y} as unsigned longs, and 0 otherwise. Assumes that x - y fits into a
099   * signed long. The implementation is branch-free, and benchmarks suggest it is measurably faster
100   * than the straightforward ternary expression.
101   */
102  @VisibleForTesting
103  static int lessThanBranchFree(long x, long y) {
104    // Returns the sign bit of x - y.
105    return (int) (~~(x - y) >>> (Long.SIZE - 1));
106  }
107
108  /**
109   * Returns the base-2 logarithm of {@code x}, rounded according to the specified rounding mode.
110   *
111   * @throws IllegalArgumentException if {@code x <= 0}
112   * @throws ArithmeticException if {@code mode} is {@link RoundingMode#UNNECESSARY} and {@code x}
113   *     is not a power of two
114   */
115  @SuppressWarnings("fallthrough")
116  // TODO(kevinb): remove after this warning is disabled globally
117  public static int log2(long x, RoundingMode mode) {
118    checkPositive("x", x);
119    switch (mode) {
120      case UNNECESSARY:
121        checkRoundingUnnecessary(isPowerOfTwo(x));
122        // fall through
123      case DOWN:
124      case FLOOR:
125        return (Long.SIZE - 1) - Long.numberOfLeadingZeros(x);
126
127      case UP:
128      case CEILING:
129        return Long.SIZE - Long.numberOfLeadingZeros(x - 1);
130
131      case HALF_DOWN:
132      case HALF_UP:
133      case HALF_EVEN:
134        // Since sqrt(2) is irrational, log2(x) - logFloor cannot be exactly 0.5
135        int leadingZeros = Long.numberOfLeadingZeros(x);
136        long cmp = MAX_POWER_OF_SQRT2_UNSIGNED >>> leadingZeros;
137        // floor(2^(logFloor + 0.5))
138        int logFloor = (Long.SIZE - 1) - leadingZeros;
139        return logFloor + lessThanBranchFree(cmp, x);
140    }
141    throw new AssertionError("impossible");
142  }
143
144  /** The biggest half power of two that fits into an unsigned long */
145  @VisibleForTesting static final long MAX_POWER_OF_SQRT2_UNSIGNED = 0xB504F333F9DE6484L;
146
147  /**
148   * Returns the base-10 logarithm of {@code x}, rounded according to the specified rounding mode.
149   *
150   * @throws IllegalArgumentException if {@code x <= 0}
151   * @throws ArithmeticException if {@code mode} is {@link RoundingMode#UNNECESSARY} and {@code x}
152   *     is not a power of ten
153   */
154  @GwtIncompatible // TODO
155  @SuppressWarnings("fallthrough")
156  // TODO(kevinb): remove after this warning is disabled globally
157  public static int log10(long x, RoundingMode mode) {
158    checkPositive("x", x);
159    int logFloor = log10Floor(x);
160    long floorPow = powersOf10[logFloor];
161    switch (mode) {
162      case UNNECESSARY:
163        checkRoundingUnnecessary(x == floorPow);
164        // fall through
165      case FLOOR:
166      case DOWN:
167        return logFloor;
168      case CEILING:
169      case UP:
170        return logFloor + lessThanBranchFree(floorPow, x);
171      case HALF_DOWN:
172      case HALF_UP:
173      case HALF_EVEN:
174        // sqrt(10) is irrational, so log10(x)-logFloor is never exactly 0.5
175        return logFloor + lessThanBranchFree(halfPowersOf10[logFloor], x);
176    }
177    throw new AssertionError();
178  }
179
180  @GwtIncompatible // TODO
181  static int log10Floor(long x) {
182    /*
183     * Based on Hacker's Delight Fig. 11-5, the two-table-lookup, branch-free implementation.
184     *
185     * The key idea is that based on the number of leading zeros (equivalently, floor(log2(x))), we
186     * can narrow the possible floor(log10(x)) values to two. For example, if floor(log2(x)) is 6,
187     * then 64 <= x < 128, so floor(log10(x)) is either 1 or 2.
188     */
189    int y = maxLog10ForLeadingZeros[Long.numberOfLeadingZeros(x)];
190    /*
191     * y is the higher of the two possible values of floor(log10(x)). If x < 10^y, then we want the
192     * lower of the two possible values, or y - 1, otherwise, we want y.
193     */
194    return y - lessThanBranchFree(x, powersOf10[y]);
195  }
196
197  // maxLog10ForLeadingZeros[i] == floor(log10(2^(Long.SIZE - i)))
198  @VisibleForTesting
199  static final byte[] maxLog10ForLeadingZeros = {
200    19, 18, 18, 18, 18, 17, 17, 17, 16, 16, 16, 15, 15, 15, 15, 14, 14, 14, 13, 13, 13, 12, 12, 12,
201    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,
202    3, 2, 2, 2, 1, 1, 1, 0, 0, 0
203  };
204
205  @GwtIncompatible // TODO
206  @VisibleForTesting
207  static final long[] powersOf10 = {
208    1L,
209    10L,
210    100L,
211    1000L,
212    10000L,
213    100000L,
214    1000000L,
215    10000000L,
216    100000000L,
217    1000000000L,
218    10000000000L,
219    100000000000L,
220    1000000000000L,
221    10000000000000L,
222    100000000000000L,
223    1000000000000000L,
224    10000000000000000L,
225    100000000000000000L,
226    1000000000000000000L
227  };
228
229  // halfPowersOf10[i] = largest long less than 10^(i + 0.5)
230  @GwtIncompatible // TODO
231  @VisibleForTesting
232  static final long[] halfPowersOf10 = {
233    3L,
234    31L,
235    316L,
236    3162L,
237    31622L,
238    316227L,
239    3162277L,
240    31622776L,
241    316227766L,
242    3162277660L,
243    31622776601L,
244    316227766016L,
245    3162277660168L,
246    31622776601683L,
247    316227766016837L,
248    3162277660168379L,
249    31622776601683793L,
250    316227766016837933L,
251    3162277660168379331L
252  };
253
254  /**
255   * Returns {@code b} to the {@code k}th power. Even if the result overflows, it will be equal to
256   * {@code BigInteger.valueOf(b).pow(k).longValue()}. This implementation runs in {@code O(log k)}
257   * time.
258   *
259   * @throws IllegalArgumentException if {@code k < 0}
260   */
261  @GwtIncompatible // TODO
262  public static long pow(long b, int k) {
263    checkNonNegative("exponent", k);
264    if (-2 <= b && b <= 2) {
265      switch ((int) b) {
266        case 0:
267          return (k == 0) ? 1 : 0;
268        case 1:
269          return 1;
270        case (-1):
271          return ((k & 1) == 0) ? 1 : -1;
272        case 2:
273          return (k < Long.SIZE) ? 1L << k : 0;
274        case (-2):
275          if (k < Long.SIZE) {
276            return ((k & 1) == 0) ? 1L << k : -(1L << k);
277          } else {
278            return 0;
279          }
280        default:
281          throw new AssertionError();
282      }
283    }
284    for (long accum = 1; ; k >>= 1) {
285      switch (k) {
286        case 0:
287          return accum;
288        case 1:
289          return accum * b;
290        default:
291          accum *= ((k & 1) == 0) ? 1 : b;
292          b *= b;
293      }
294    }
295  }
296
297  /**
298   * Returns the square root of {@code x}, rounded with the specified rounding mode.
299   *
300   * @throws IllegalArgumentException if {@code x < 0}
301   * @throws ArithmeticException if {@code mode} is {@link RoundingMode#UNNECESSARY} and {@code
302   *     sqrt(x)} is not an integer
303   */
304  @GwtIncompatible // TODO
305  public static long sqrt(long x, RoundingMode mode) {
306    checkNonNegative("x", x);
307    if (fitsInInt(x)) {
308      return IntMath.sqrt((int) x, mode);
309    }
310    /*
311     * Let k be the true value of floor(sqrt(x)), so that
312     *
313     *            k * k <= x          <  (k + 1) * (k + 1)
314     * (double) (k * k) <= (double) x <= (double) ((k + 1) * (k + 1))
315     *          since casting to double is nondecreasing.
316     *          Note that the right-hand inequality is no longer strict.
317     * Math.sqrt(k * k) <= Math.sqrt(x) <= Math.sqrt((k + 1) * (k + 1))
318     *          since Math.sqrt is monotonic.
319     * (long) Math.sqrt(k * k) <= (long) Math.sqrt(x) <= (long) Math.sqrt((k + 1) * (k + 1))
320     *          since casting to long is monotonic
321     * k <= (long) Math.sqrt(x) <= k + 1
322     *          since (long) Math.sqrt(k * k) == k, as checked exhaustively in
323     *          {@link LongMathTest#testSqrtOfPerfectSquareAsDoubleIsPerfect}
324     */
325    long guess = (long) Math.sqrt((double) x);
326    // Note: guess is always <= FLOOR_SQRT_MAX_LONG.
327    long guessSquared = guess * guess;
328    // Note (2013-2-26): benchmarks indicate that, inscrutably enough, using if statements is
329    // faster here than using lessThanBranchFree.
330    switch (mode) {
331      case UNNECESSARY:
332        checkRoundingUnnecessary(guessSquared == x);
333        return guess;
334      case FLOOR:
335      case DOWN:
336        if (x < guessSquared) {
337          return guess - 1;
338        }
339        return guess;
340      case CEILING:
341      case UP:
342        if (x > guessSquared) {
343          return guess + 1;
344        }
345        return guess;
346      case HALF_DOWN:
347      case HALF_UP:
348      case HALF_EVEN:
349        long sqrtFloor = guess - ((x < guessSquared) ? 1 : 0);
350        long halfSquare = sqrtFloor * sqrtFloor + sqrtFloor;
351        /*
352         * We wish to test whether or not x <= (sqrtFloor + 0.5)^2 = halfSquare + 0.25. Since both x
353         * and halfSquare are integers, this is equivalent to testing whether or not x <=
354         * halfSquare. (We have to deal with overflow, though.)
355         *
356         * If we treat halfSquare as an unsigned long, we know that
357         *            sqrtFloor^2 <= x < (sqrtFloor + 1)^2
358         * halfSquare - sqrtFloor <= x < halfSquare + sqrtFloor + 1
359         * so |x - halfSquare| <= sqrtFloor.  Therefore, it's safe to treat x - halfSquare as a
360         * signed long, so lessThanBranchFree is safe for use.
361         */
362        return sqrtFloor + lessThanBranchFree(halfSquare, x);
363    }
364    throw new AssertionError();
365  }
366
367  /**
368   * Returns the result of dividing {@code p} by {@code q}, rounding using the specified {@code
369   * RoundingMode}.
370   *
371   * @throws ArithmeticException if {@code q == 0}, or if {@code mode == UNNECESSARY} and {@code a}
372   *     is not an integer multiple of {@code b}
373   */
374  @GwtIncompatible // TODO
375  @SuppressWarnings("fallthrough")
376  public static long divide(long p, long q, RoundingMode mode) {
377    checkNotNull(mode);
378    long div = p / q; // throws if q == 0
379    long rem = p - q * div; // equals p % q
380
381    if (rem == 0) {
382      return div;
383    }
384
385    /*
386     * Normal Java division rounds towards 0, consistently with RoundingMode.DOWN. We just have to
387     * deal with the cases where rounding towards 0 is wrong, which typically depends on the sign of
388     * p / q.
389     *
390     * signum is 1 if p and q are both nonnegative or both negative, and -1 otherwise.
391     */
392    int signum = 1 | (int) ((p ^ q) >> (Long.SIZE - 1));
393    boolean increment;
394    switch (mode) {
395      case UNNECESSARY:
396        checkRoundingUnnecessary(rem == 0);
397        // fall through
398      case DOWN:
399        increment = false;
400        break;
401      case UP:
402        increment = true;
403        break;
404      case CEILING:
405        increment = signum > 0;
406        break;
407      case FLOOR:
408        increment = signum < 0;
409        break;
410      case HALF_EVEN:
411      case HALF_DOWN:
412      case HALF_UP:
413        long absRem = abs(rem);
414        long cmpRemToHalfDivisor = absRem - (abs(q) - absRem);
415        // subtracting two nonnegative longs can't overflow
416        // cmpRemToHalfDivisor has the same sign as compare(abs(rem), abs(q) / 2).
417        if (cmpRemToHalfDivisor == 0) { // exactly on the half mark
418          increment = (mode == HALF_UP || (mode == HALF_EVEN && (div & 1) != 0));
419        } else {
420          increment = cmpRemToHalfDivisor > 0; // closer to the UP value
421        }
422        break;
423      default:
424        throw new AssertionError();
425    }
426    return increment ? div + signum : div;
427  }
428
429  /**
430   * Returns {@code x mod m}, a non-negative value less than {@code m}. This differs from {@code x %
431   * m}, which might be negative.
432   *
433   * <p>For example:
434   *
435   * <pre>{@code
436   * mod(7, 4) == 3
437   * mod(-7, 4) == 1
438   * mod(-1, 4) == 3
439   * mod(-8, 4) == 0
440   * mod(8, 4) == 0
441   * }</pre>
442   *
443   * @throws ArithmeticException if {@code m <= 0}
444   * @see <a href="http://docs.oracle.com/javase/specs/jls/se7/html/jls-15.html#jls-15.17.3">
445   *     Remainder Operator</a>
446   */
447  @GwtIncompatible // TODO
448  public static int mod(long x, int m) {
449    // Cast is safe because the result is guaranteed in the range [0, m)
450    return (int) mod(x, (long) m);
451  }
452
453  /**
454   * Returns {@code x mod m}, a non-negative value less than {@code m}. This differs from {@code x %
455   * m}, which might be negative.
456   *
457   * <p>For example:
458   *
459   * <pre>{@code
460   * mod(7, 4) == 3
461   * mod(-7, 4) == 1
462   * mod(-1, 4) == 3
463   * mod(-8, 4) == 0
464   * mod(8, 4) == 0
465   * }</pre>
466   *
467   * @throws ArithmeticException if {@code m <= 0}
468   * @see <a href="http://docs.oracle.com/javase/specs/jls/se7/html/jls-15.html#jls-15.17.3">
469   *     Remainder Operator</a>
470   */
471  @GwtIncompatible // TODO
472  public static long mod(long x, long m) {
473    if (m <= 0) {
474      throw new ArithmeticException("Modulus must be positive");
475    }
476    long result = x % m;
477    return (result >= 0) ? result : result + m;
478  }
479
480  /**
481   * Returns the greatest common divisor of {@code a, b}. Returns {@code 0} if {@code a == 0 && b ==
482   * 0}.
483   *
484   * @throws IllegalArgumentException if {@code a < 0} or {@code b < 0}
485   */
486  public static long gcd(long a, long b) {
487    /*
488     * The reason we require both arguments to be >= 0 is because otherwise, what do you return on
489     * gcd(0, Long.MIN_VALUE)? BigInteger.gcd would return positive 2^63, but positive 2^63 isn't an
490     * int.
491     */
492    checkNonNegative("a", a);
493    checkNonNegative("b", b);
494    if (a == 0) {
495      // 0 % b == 0, so b divides a, but the converse doesn't hold.
496      // BigInteger.gcd is consistent with this decision.
497      return b;
498    } else if (b == 0) {
499      return a; // similar logic
500    }
501    /*
502     * Uses the binary GCD algorithm; see http://en.wikipedia.org/wiki/Binary_GCD_algorithm. This is
503     * >60% faster than the Euclidean algorithm in benchmarks.
504     */
505    int aTwos = Long.numberOfTrailingZeros(a);
506    a >>= aTwos; // divide out all 2s
507    int bTwos = Long.numberOfTrailingZeros(b);
508    b >>= bTwos; // divide out all 2s
509    while (a != b) { // both a, b are odd
510      // The key to the binary GCD algorithm is as follows:
511      // Both a and b are odd. Assume a > b; then gcd(a - b, b) = gcd(a, b).
512      // But in gcd(a - b, b), a - b is even and b is odd, so we can divide out powers of two.
513
514      // We bend over backwards to avoid branching, adapting a technique from
515      // http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax
516
517      long delta = a - b; // can't overflow, since a and b are nonnegative
518
519      long minDeltaOrZero = delta & (delta >> (Long.SIZE - 1));
520      // equivalent to Math.min(delta, 0)
521
522      a = delta - minDeltaOrZero - minDeltaOrZero; // sets a to Math.abs(a - b)
523      // a is now nonnegative and even
524
525      b += minDeltaOrZero; // sets b to min(old a, b)
526      a >>= Long.numberOfTrailingZeros(a); // divide out all 2s, since 2 doesn't divide b
527    }
528    return a << min(aTwos, bTwos);
529  }
530
531  /**
532   * Returns the sum of {@code a} and {@code b}, provided it does not overflow.
533   *
534   * @throws ArithmeticException if {@code a + b} overflows in signed {@code long} arithmetic
535   */
536  // Whenever both tests are cheap and functional, it's faster to use &, | instead of &&, ||
537  @SuppressWarnings("ShortCircuitBoolean")
538  public static long checkedAdd(long a, long b) {
539    long result = a + b;
540    checkNoOverflow((a ^ b) < 0 | (a ^ result) >= 0, "checkedAdd", a, b);
541    return result;
542  }
543
544  /**
545   * Returns the difference of {@code a} and {@code b}, provided it does not overflow.
546   *
547   * @throws ArithmeticException if {@code a - b} overflows in signed {@code long} arithmetic
548   */
549  // Whenever both tests are cheap and functional, it's faster to use &, | instead of &&, ||
550  @SuppressWarnings("ShortCircuitBoolean")
551  public static long checkedSubtract(long a, long b) {
552    long result = a - b;
553    checkNoOverflow((a ^ b) >= 0 | (a ^ result) >= 0, "checkedSubtract", a, b);
554    return result;
555  }
556
557  /**
558   * Returns the product of {@code a} and {@code b}, provided it does not overflow.
559   *
560   * @throws ArithmeticException if {@code a * b} overflows in signed {@code long} arithmetic
561   */
562  // Whenever both tests are cheap and functional, it's faster to use &, | instead of &&, ||
563  @SuppressWarnings("ShortCircuitBoolean")
564  public static long checkedMultiply(long a, long b) {
565    // Hacker's Delight, Section 2-12
566    int leadingZeros =
567        Long.numberOfLeadingZeros(a)
568            + Long.numberOfLeadingZeros(~a)
569            + Long.numberOfLeadingZeros(b)
570            + Long.numberOfLeadingZeros(~b);
571    /*
572     * If leadingZeros > Long.SIZE + 1 it's definitely fine, if it's < Long.SIZE it's definitely
573     * bad. We do the leadingZeros check to avoid the division below if at all possible.
574     *
575     * Otherwise, if b == Long.MIN_VALUE, then the only allowed values of a are 0 and 1. We take
576     * care of all a < 0 with their own check, because in particular, the case a == -1 will
577     * incorrectly pass the division check below.
578     *
579     * In all other cases, we check that either a is 0 or the result is consistent with division.
580     */
581    if (leadingZeros > Long.SIZE + 1) {
582      return a * b;
583    }
584    checkNoOverflow(leadingZeros >= Long.SIZE, "checkedMultiply", a, b);
585    checkNoOverflow(a >= 0 | b != Long.MIN_VALUE, "checkedMultiply", a, b);
586    long result = a * b;
587    checkNoOverflow(a == 0 || result / a == b, "checkedMultiply", a, b);
588    return result;
589  }
590
591  /**
592   * Returns the {@code b} to the {@code k}th power, provided it does not overflow.
593   *
594   * @throws ArithmeticException if {@code b} to the {@code k}th power overflows in signed {@code
595   *     long} arithmetic
596   */
597  @GwtIncompatible // TODO
598  // Whenever both tests are cheap and functional, it's faster to use &, | instead of &&, ||
599  @SuppressWarnings("ShortCircuitBoolean")
600  public static long checkedPow(long b, int k) {
601    checkNonNegative("exponent", k);
602    if (b >= -2 & b <= 2) {
603      switch ((int) b) {
604        case 0:
605          return (k == 0) ? 1 : 0;
606        case 1:
607          return 1;
608        case (-1):
609          return ((k & 1) == 0) ? 1 : -1;
610        case 2:
611          checkNoOverflow(k < Long.SIZE - 1, "checkedPow", b, k);
612          return 1L << k;
613        case (-2):
614          checkNoOverflow(k < Long.SIZE, "checkedPow", b, k);
615          return ((k & 1) == 0) ? (1L << k) : (-1L << k);
616        default:
617          throw new AssertionError();
618      }
619    }
620    long accum = 1;
621    while (true) {
622      switch (k) {
623        case 0:
624          return accum;
625        case 1:
626          return checkedMultiply(accum, b);
627        default:
628          if ((k & 1) != 0) {
629            accum = checkedMultiply(accum, b);
630          }
631          k >>= 1;
632          if (k > 0) {
633            checkNoOverflow(
634                -FLOOR_SQRT_MAX_LONG <= b && b <= FLOOR_SQRT_MAX_LONG, "checkedPow", b, k);
635            b *= b;
636          }
637      }
638    }
639  }
640
641  /**
642   * Returns the sum of {@code a} and {@code b} unless it would overflow or underflow in which case
643   * {@code Long.MAX_VALUE} or {@code Long.MIN_VALUE} is returned, respectively.
644   *
645   * @since 20.0
646   */
647  // Whenever both tests are cheap and functional, it's faster to use &, | instead of &&, ||
648  @SuppressWarnings("ShortCircuitBoolean")
649  public static long saturatedAdd(long a, long b) {
650    long naiveSum = a + b;
651    if ((a ^ b) < 0 | (a ^ naiveSum) >= 0) {
652      // If a and b have different signs or a has the same sign as the result then there was no
653      // overflow, return.
654      return naiveSum;
655    }
656    // we did over/under flow, if the sign is negative we should return MAX otherwise MIN
657    return Long.MAX_VALUE + ((naiveSum >>> (Long.SIZE - 1)) ^ 1);
658  }
659
660  /**
661   * Returns the difference of {@code a} and {@code b} unless it would overflow or underflow in
662   * which case {@code Long.MAX_VALUE} or {@code Long.MIN_VALUE} is returned, respectively.
663   *
664   * @since 20.0
665   */
666  // Whenever both tests are cheap and functional, it's faster to use &, | instead of &&, ||
667  @SuppressWarnings("ShortCircuitBoolean")
668  public static long saturatedSubtract(long a, long b) {
669    long naiveDifference = a - b;
670    if ((a ^ b) >= 0 | (a ^ naiveDifference) >= 0) {
671      // If a and b have the same signs or a has the same sign as the result then there was no
672      // overflow, return.
673      return naiveDifference;
674    }
675    // we did over/under flow
676    return Long.MAX_VALUE + ((naiveDifference >>> (Long.SIZE - 1)) ^ 1);
677  }
678
679  /**
680   * Returns the product of {@code a} and {@code b} unless it would overflow or underflow in which
681   * case {@code Long.MAX_VALUE} or {@code Long.MIN_VALUE} is returned, respectively.
682   *
683   * @since 20.0
684   */
685  // Whenever both tests are cheap and functional, it's faster to use &, | instead of &&, ||
686  @SuppressWarnings("ShortCircuitBoolean")
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  // Whenever both tests are cheap and functional, it's faster to use &, | instead of &&, ||
717  @SuppressWarnings("ShortCircuitBoolean")
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 divisibility 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  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 = 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 Long.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 = Long.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 = Long.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}