Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /*
   * Copyright (C) 2011 The Guava Authors
   *
   * Licensed under the Apache License, Version 2.0 (the "License");
   * you may not use this file except in compliance with the License.
   * You may obtain a copy of the License at
   *
   * http://www.apache.org/licenses/LICENSE-2.0
   *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
 
 package com.google.common.math;
 
 import static com.google.common.base.Preconditions.checkArgument;
 import static com.google.common.base.Preconditions.checkNotNull;
 import static com.google.common.math.MathPreconditions.checkNoOverflow;
 import static com.google.common.math.MathPreconditions.checkNonNegative;
 import static com.google.common.math.MathPreconditions.checkPositive;
 import static com.google.common.math.MathPreconditions.checkRoundingUnnecessary;
 import static java.lang.Math.abs;
 import static java.lang.Math.min;
 import static java.math.RoundingMode.HALF_EVEN;
 import static java.math.RoundingMode.HALF_UP;
 
 
A class for arithmetic on values of type int. Where possible, methods are defined and named analogously to their BigInteger counterparts.

The implementations of many methods in this class are based on material from Henry S. Warren, Jr.'s Hacker's Delight, (Addison Wesley, 2002).

Similar functionality for long and for java.math.BigInteger can be found in LongMath and BigIntegerMath respectively. For other common operations on int values, see com.google.common.primitives.Ints.

Author(s):
Louis Wasserman
Since:
11.0
 
 @GwtCompatible(emulated = true)
 public final class IntMath {
   // NOTE: Whenever both tests are cheap and functional, it's faster to use &, | instead of &&, ||
 
  
Returns true if x represents a power of two.

This differs from Integer.bitCount(x) == 1, because Integer.bitCount(Integer.MIN_VALUE) == 1, but java.lang.Integer.MIN_VALUE is not a power of two.

 
   public static boolean isPowerOfTwo(int x) {
     return x > 0 & (x & (x - 1)) == 0;
   }
  
  
Returns 1 if x < y as unsigned integers, and 0 otherwise. Assumes that x - y fits into a signed int. The implementation is branch-free, and benchmarks suggest it is measurably (if narrowly) faster than the straightforward ternary expression.
 
   static int lessThanBranchFree(int xint y) {
     // The double negation is optimized away by normal Java, but is necessary for GWT
     // to make sure bit twiddling works as expected.
     return ~~(x - y) >>> (. - 1);
   }

  
Returns the base-2 logarithm of x, rounded according to the specified rounding mode.

 
   @SuppressWarnings("fallthrough")
   // TODO(kevinb): remove after this warning is disabled globally
   public static int log2(int xRoundingMode mode) {
     checkPositive("x"x);
     switch (mode) {
       case :
         // fall through
       case :
       case :
         return (. - 1) - Integer.numberOfLeadingZeros(x);
 
       case :
       case :
         return . - Integer.numberOfLeadingZeros(x - 1);
      case :
      case :
      case :
        // Since sqrt(2) is irrational, log2(x) - logFloor cannot be exactly 0.5
        int leadingZeros = Integer.numberOfLeadingZeros(x);
        int cmp =  >>> leadingZeros;
          // floor(2^(logFloor + 0.5))
        int logFloor = (. - 1) - leadingZeros;
        return logFloor + lessThanBranchFree(cmpx);
      default:
        throw new AssertionError();
    }
  }

  
The biggest half power of two that can fit in an unsigned int.
  @VisibleForTesting static final int MAX_POWER_OF_SQRT2_UNSIGNED = 0xB504F333;

  
Returns the base-10 logarithm of x, rounded according to the specified rounding mode.

  @GwtIncompatible("need BigIntegerMath to adequately test")
  @SuppressWarnings("fallthrough")
  public static int log10(int xRoundingMode mode) {
    checkPositive("x"x);
    int logFloor = log10Floor(x);
    int floorPow = [logFloor];
    switch (mode) {
      case :
        checkRoundingUnnecessary(x == floorPow);
        // fall through
      case :
      case :
        return logFloor;
      case :
      case :
        return logFloor + lessThanBranchFree(floorPowx);
      case :
      case :
      case :
        // sqrt(10) is irrational, so log10(x) - logFloor is never exactly 0.5
        return logFloor + lessThanBranchFree([logFloor], x);
      default:
        throw new AssertionError();
    }
  }
  private static int log10Floor(int x) {
    /*
     * Based on Hacker's Delight Fig. 11-5, the two-table-lookup, branch-free implementation.
     *
     * The key idea is that based on the number of leading zeros (equivalently, floor(log2(x))),
     * we can narrow the possible floor(log10(x)) values to two.  For example, if floor(log2(x))
     * is 6, then 64 <= x < 128, so floor(log10(x)) is either 1 or 2.
     */
    int y = [Integer.numberOfLeadingZeros(x)];
    /*
     * y is the higher of the two possible values of floor(log10(x)). If x < 10^y, then we want the
     * lower of the two possible values, or y - 1, otherwise, we want y.
     */
    return y - lessThanBranchFree(x[y]);
  }
  // maxLog10ForLeadingZeros[i] == floor(log10(2^(Long.SIZE - i)))
  @VisibleForTesting static final byte[] maxLog10ForLeadingZeros = {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, 0};
  @VisibleForTesting static final int[] powersOf10 = {1, 10, 100, 1000, 10000,
    100000, 1000000, 10000000, 100000000, 1000000000};
  // halfPowersOf10[i] = largest int less than 10^(i + 0.5)
  @VisibleForTesting static final int[] halfPowersOf10 =
      {3, 31, 316, 3162, 31622, 316227, 3162277, 31622776, 316227766, .};

  
Returns b to the kth power. Even if the result overflows, it will be equal to BigInteger.valueOf(b).pow(k).intValue(). This implementation runs in O(log k) time.

Compare checkedPow(int,int), which throws an java.lang.ArithmeticException upon overflow.

  @GwtIncompatible("failing tests")
  public static int pow(int bint k) {
    checkNonNegative("exponent"k);
    switch (b) {
      case 0:
        return (k == 0) ? 1 : 0;
      case 1:
        return 1;
      case (-1):
        return ((k & 1) == 0) ? 1 : -1;
      case 2:
        return (k < .) ? (1 << k) : 0;
      case (-2):
        if (k < .) {
          return ((k & 1) == 0) ? (1 << k) : -(1 << k);
        } else {
          return 0;
        }
      default:
        // continue below to handle the general case
    }
    for (int accum = 1;; k >>= 1) {
      switch (k) {
        case 0:
          return accum;
        case 1:
          return b * accum;
        default:
          accum *= ((k & 1) == 0) ? 1 : b;
          b *= b;
      }
    }
  }

  
Returns the square root of x, rounded with the specified rounding mode.

  @GwtIncompatible("need BigIntegerMath to adequately test")
  @SuppressWarnings("fallthrough")
  public static int sqrt(int xRoundingMode mode) {
    checkNonNegative("x"x);
    int sqrtFloor = sqrtFloor(x);
    switch (mode) {
      case :
        checkRoundingUnnecessary(sqrtFloor * sqrtFloor == x); // fall through
      case :
      case :
        return sqrtFloor;
      case :
      case :
        return sqrtFloor + lessThanBranchFree(sqrtFloor * sqrtFloorx);
      case :
      case :
      case :
        int halfSquare = sqrtFloor * sqrtFloor + sqrtFloor;
        /*
         * We wish to test whether or not x <= (sqrtFloor + 0.5)^2 = halfSquare + 0.25. Since both
         * x and halfSquare are integers, this is equivalent to testing whether or not x <=
         * halfSquare. (We have to deal with overflow, though.)
         * 
         * If we treat halfSquare as an unsigned int, we know that
         *            sqrtFloor^2 <= x < (sqrtFloor + 1)^2
         * halfSquare - sqrtFloor <= x < halfSquare + sqrtFloor + 1
         * so |x - halfSquare| <= sqrtFloor.  Therefore, it's safe to treat x - halfSquare as a
         * signed int, so lessThanBranchFree is safe for use.
         */
        return sqrtFloor + lessThanBranchFree(halfSquarex);
      default:
        throw new AssertionError();
    }
  }
  private static int sqrtFloor(int x) {
    // There is no loss of precision in converting an int to a double, according to
    // http://java.sun.com/docs/books/jls/third_edition/html/conversions.html#5.1.2
    return (int) Math.sqrt(x);
  }

  
Returns the result of dividing p by q, rounding using the specified RoundingMode.

Throws:
java.lang.ArithmeticException if q == 0, or if mode == UNNECESSARY and a is not an integer multiple of b
  @SuppressWarnings("fallthrough")
  public static int divide(int pint qRoundingMode mode) {
    checkNotNull(mode);
    if (q == 0) {
      throw new ArithmeticException("/ by zero"); // for GWT
    }
    int div = p / q;
    int rem = p - q * div// equal to p % q
    if (rem == 0) {
      return div;
    }
    /*
     * Normal Java division rounds towards 0, consistently with RoundingMode.DOWN. We just have to
     * deal with the cases where rounding towards 0 is wrong, which typically depends on the sign of
     * p / q.
     *
     * signum is 1 if p and q are both nonnegative or both negative, and -1 otherwise.
     */
    int signum = 1 | ((p ^ q) >> (. - 1));
    boolean increment;
    switch (mode) {
      case :
        checkRoundingUnnecessary(rem == 0);
        // fall through
      case :
        increment = false;
        break;
      case :
        increment = true;
        break;
      case :
        increment = signum > 0;
        break;
      case :
        increment = signum < 0;
        break;
      case :
      case :
      case :
        int absRem = abs(rem);
        int cmpRemToHalfDivisor = absRem - (abs(q) - absRem);
        // subtracting two nonnegative ints can't overflow
        // cmpRemToHalfDivisor has the same sign as compare(abs(rem), abs(q) / 2).
        if (cmpRemToHalfDivisor == 0) { // exactly on the half mark
          increment = (mode ==  || (mode ==  & (div & 1) != 0));
        } else {
          increment = cmpRemToHalfDivisor > 0; // closer to the UP value
        }
        break;
      default:
        throw new AssertionError();
    }
    return increment ? div + signum : div;
  }

  
Returns x mod m. This differs from x % m in that it always returns a non-negative result.

For example:

 mod(7, 4) == 3
 mod(-7, 4) == 1
 mod(-1, 4) == 3
 mod(-8, 4) == 0
 mod(8, 4) == 0

  public static int mod(int xint m) {
    if (m <= 0) {
      throw new ArithmeticException("Modulus " + m + " must be > 0");
    }
    int result = x % m;
    return (result >= 0) ? result : result + m;
  }

  
Returns the greatest common divisor of a, b. Returns 0 if a == 0 && b == 0.

Throws:
java.lang.IllegalArgumentException if a < 0 or b < 0
  public static int gcd(int aint b) {
    /*
     * The reason we require both arguments to be >= 0 is because otherwise, what do you return on
     * gcd(0, Integer.MIN_VALUE)? BigInteger.gcd would return positive 2^31, but positive 2^31
     * isn't an int.
     */
    checkNonNegative("a"a);
    checkNonNegative("b"b);
    if (a == 0) {
      // 0 % b == 0, so b divides a, but the converse doesn't hold.
      // BigInteger.gcd is consistent with this decision.
      return b;
    } else if (b == 0) {
      return a// similar logic
    }
    /*
     * Uses the binary GCD algorithm; see http://en.wikipedia.org/wiki/Binary_GCD_algorithm.
     * This is >40% faster than the Euclidean algorithm in benchmarks.
     */
    int aTwos = Integer.numberOfTrailingZeros(a);
    a >>= aTwos// divide out all 2s
    int bTwos = Integer.numberOfTrailingZeros(b);
    b >>= bTwos// divide out all 2s
    while (a != b) { // both a, b are odd
      // The key to the binary GCD algorithm is as follows:
      // Both a and b are odd.  Assume a > b; then gcd(a - b, b) = gcd(a, b).
      // But in gcd(a - b, b), a - b is even and b is odd, so we can divide out powers of two.
      // We bend over backwards to avoid branching, adapting a technique from
      // http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax
      int delta = a - b// can't overflow, since a and b are nonnegative
      int minDeltaOrZero = delta & (delta >> (. - 1));
      // equivalent to Math.min(delta, 0)
      a = delta - minDeltaOrZero - minDeltaOrZero// sets a to Math.abs(a - b)
      // a is now nonnegative and even
      b += minDeltaOrZero// sets b to min(old a, b)
      a >>= Integer.numberOfTrailingZeros(a); // divide out all 2s, since 2 doesn't divide b
    }
    return a << min(aTwosbTwos);
  }

  
Returns the sum of a and b, provided it does not overflow.

Throws:
java.lang.ArithmeticException if a + b overflows in signed int arithmetic
  public static int checkedAdd(int aint b) {
    long result = (longa + b;
    checkNoOverflow(result == (intresult);
    return (intresult;
  }

  
Returns the difference of a and b, provided it does not overflow.

Throws:
java.lang.ArithmeticException if a - b overflows in signed int arithmetic
  public static int checkedSubtract(int aint b) {
    long result = (longa - b;
    checkNoOverflow(result == (intresult);
    return (intresult;
  }

  
Returns the product of a and b, provided it does not overflow.

Throws:
java.lang.ArithmeticException if a * b overflows in signed int arithmetic
  public static int checkedMultiply(int aint b) {
    long result = (longa * b;
    checkNoOverflow(result == (intresult);
    return (intresult;
  }

  
Returns the b to the kth power, provided it does not overflow.

pow(int,int) may be faster, but does not check for overflow.

Throws:
java.lang.ArithmeticException if b to the kth power overflows in signed int arithmetic
  public static int checkedPow(int bint k) {
    checkNonNegative("exponent"k);
    switch (b) {
      case 0:
        return (k == 0) ? 1 : 0;
      case 1:
        return 1;
      case (-1):
        return ((k & 1) == 0) ? 1 : -1;
      case 2:
        checkNoOverflow(k < . - 1);
        return 1 << k;
      case (-2):
        checkNoOverflow(k < .);
        return ((k & 1) == 0) ? 1 << k : -1 << k;
      default:
        // continue below to handle the general case
    }
    int accum = 1;
    while (true) {
      switch (k) {
        case 0:
          return accum;
        case 1:
          return checkedMultiply(accumb);
        default:
          if ((k & 1) != 0) {
            accum = checkedMultiply(accumb);
          }
          k >>= 1;
          if (k > 0) {
            checkNoOverflow(- <= b & b <= );
            b *= b;
          }
      }
    }
  }
  @VisibleForTesting static final int FLOOR_SQRT_MAX_INT = 46340;

  
Returns n!, that is, the product of the first n positive integers, 1 if n == 0, or java.lang.Integer.MAX_VALUE if the result does not fit in a int.

  public static int factorial(int n) {
    checkNonNegative("n"n);
    return (n < .) ? [n] : .;
  }
  private static final int[] factorials = {
      1,
      1,
      1 * 2,
      1 * 2 * 3,
      1 * 2 * 3 * 4,
      1 * 2 * 3 * 4 * 5,
      1 * 2 * 3 * 4 * 5 * 6,
      1 * 2 * 3 * 4 * 5 * 6 * 7,
      1 * 2 * 3 * 4 * 5 * 6 * 7 * 8,
      1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9,
      1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10,
      1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11,
      1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12};

  
Returns n choose k, also known as the binomial coefficient of n and k, or java.lang.Integer.MAX_VALUE if the result does not fit in an int.

Throws:
java.lang.IllegalArgumentException if n < 0, k < 0 or k > n
  @GwtIncompatible("need BigIntegerMath to adequately test")
  public static int binomial(int nint k) {
    checkNonNegative("n"n);
    checkNonNegative("k"k);
    checkArgument(k <= n"k (%s) > n (%s)"kn);
    if (k > (n >> 1)) {
      k = n - k;
    }
    if (k >= . || n > [k]) {
      return .;
    }
    switch (k) {
      case 0:
        return 1;
      case 1:
        return n;
      default:
        long result = 1;
        for (int i = 0; i < ki++) {
          result *= n - i;
          result /= i + 1;
        }
        return (intresult;
    }
  }
  // binomial(biggestBinomials[k], k) fits in an int, but not binomial(biggestBinomials[k]+1,k).
  @VisibleForTesting static int[] biggestBinomials = {
    65536,
    2345,
    477,
    193,
    110,
    75,
    58,
    49,
    43,
    39,
    37,
    35,
    34,
    34,
    33
  };

  
Returns the arithmetic mean of x and y, rounded towards negative infinity. This method is overflow resilient.

Since:
14.0
  public static int mean(int xint y) {
    // Efficient method for computing the arithmetic mean.
    // The alternative (x + y) / 2 fails for large values.
    // The alternative (x + y) >>> 1 fails for negative values.
    return (x & y) + ((x ^ y) >> 1);
  }
  private IntMath() {}
New to GrepCode? Check out our FAQ X