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