/**
* Returns a pseudorandom, uniformly distributed <tt>int</tt> value
* between 0 (inclusive) and the specified value (exclusive), drawn from
* this random number generator's sequence. The general contract of
* <tt>nextInt</tt> is that one <tt>int</tt> value in the specified range
* is pseudorandomly generated and returned. All <tt>n</tt> possible
* <tt>int</tt> values are produced with (approximately) equal
* probability. The method <tt>nextInt(int n)</tt> is implemented by
* class <tt>Random</tt> as follows:
* <blockquote><pre>
* public int nextInt(int n) {
* if (n<=0)
* throw new IllegalArgumentException("n must be positive");
*
* if ((n & -n) == n) // i.e., n is a power of 2
* return (int)((n * (long)next(31)) >> 31);
*
* int bits, val;
* do {
* bits = next(31);
* val = bits % n;
* } while(bits - val + (n-1) < 0);
* return val;
* }
* </pre></blockquote>
* <p>
* The hedge "approximately" is used in the foregoing description only
* because the next method is only approximately an unbiased source of
* independently chosen bits. If it were a perfect source of randomly
* chosen bits, then the algorithm shown would choose <tt>int</tt>
* values from the stated range with perfect uniformity.
* <p>
* The algorithm is slightly tricky. It rejects values that would result
* in an uneven distribution (due to the fact that 2^31 is not divisible
* by n). The probability of a value being rejected depends on n. The
* worst case is n=2^30+1, for which the probability of a reject is 1/2,
* and the expected number of iterations before the loop terminates is 2.
* <p>
* The algorithm treats the case where n is a power of two specially: it
* returns the correct number of high-order bits from the underlying
* pseudo-random number generator. In the absence of special treatment,
* the correct number of <i>low-order</i> bits would be returned. Linear
* congruential pseudo-random number generators such as the one
* implemented by this class are known to have short periods in the
* sequence of values of their low-order bits. Thus, this special case
* greatly increases the length of the sequence of values returned by
* successive calls to this method if n is a small power of two.
*
* @param n the bound on the random number to be returned. Must be
* positive.
* @return a pseudorandom, uniformly distributed <tt>int</tt>
* value between 0 (inclusive) and n (exclusive).
* @exception IllegalArgumentException n is not positive.
* @since 1.2
*/
public int nextInt(int n) {
if (n<=0)
throw new IllegalArgumentException("n must be positive");
if ((n & -n) == n) // i.e., n is a power of 2
return (int)((n * (long)next(31)) >> 31);
int bits, val;
do {
bits = next(31);
val = bits % n;
} while(bits - val + (n-1) < 0);
return val;
}
