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