日期:2014-05-20  浏览次数:20791 次

nextInt*()函数源代码的解释 求助
返回0——n-1随机数的函数  
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);//--------------------------------next(31)是什么意思,最好能把整个程序解释一遍,非常感谢 
  val = bits % n;
  } while (bits - val + (n-1) < 0);
  return val;
 }



------解决方案--------------------
next(31)是调用java.util.Random的next(int bits)。
可以看一下next(int bits)的实现
Java code

   protected int next(int bits) {
        long oldseed, nextseed;
        AtomicLong seed = this.seed;
        do {
        oldseed = seed.get();
        nextseed = (oldseed * multiplier + addend) & mask;
        } while (!seed.compareAndSet(oldseed, nextseed));
        return (int)(nextseed >>> (48 - bits));
    }

------解决方案--------------------
Random#next 方法内部会产生一个 48 位二进制位的随机数,用 next(31) 时会移除低 17 位,剩下一个高 31 位的二进制位的随机数。

因为只有 31 位才能保证 32 位的 int 值是大于等于 0 的,不至于随机出一个负数来。
------解决方案--------------------
next(31)楼上已解释。循环是为保证均匀。
举个例子,现提供一随机源rand()给你,可产生[0,100)的均匀分布随机值,要以此得到[0,30)内均匀分布的随机值。
若简单进行 rand()%30, 则[0,10)内的数出现几率比[10,30)内的要多1/3。因[0,10),[40,50),[70,80),[90,100)这四部分的数取余后都在[0,10)内。而其它数只有3个区间。为公平,若rand()产生的数在[90,100)时,丢掉重试。
以此类推,若rand()产生[0,m)的随机值,要产生[0,n)其中n<=m的随机值,
设m=kn+q (0<=q<n),为保证公平,可当rand()产生的值在 [m-q, m)时,重试。

该代码还有个小技巧:
循环的条件,楼主可理解为 
bits - val + (n-1) >= 2的31次方。
之所以可用<0代替,因为java中int是32位,最高位看成了符号位。相加后>=2^31,实际就是常说的整数溢出。