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