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