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