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
017 package com.google.common.math;
018
019 import static com.google.common.base.Preconditions.checkArgument;
020 import static com.google.common.base.Preconditions.checkNotNull;
021 import static com.google.common.math.MathPreconditions.checkNoOverflow;
022 import static com.google.common.math.MathPreconditions.checkNonNegative;
023 import static com.google.common.math.MathPreconditions.checkPositive;
024 import static com.google.common.math.MathPreconditions.checkRoundingUnnecessary;
025 import static java.lang.Math.abs;
026 import static java.lang.Math.min;
027 import static java.math.RoundingMode.HALF_EVEN;
028 import static java.math.RoundingMode.HALF_UP;
029
030 import com.google.common.annotations.Beta;
031 import com.google.common.annotations.GwtCompatible;
032 import com.google.common.annotations.GwtIncompatible;
033 import com.google.common.annotations.VisibleForTesting;
034
035 import java.math.BigInteger;
036 import 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)
054 public 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 }