了解 Java 具有绑定算法的随机下一个整数

Question

我正在研究 Java Random 库在给定上限的情况下生成整数的方式，但我不太了解该算法。在文档中它说：

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.

但我真的不明白这个实现是如何考虑到这一点的，特别是代码中的 while 条件。在我看来，这似乎（几乎）总是以 50% 的成功率成功。特别是在查看 bound 的非常低的值时（我认为在施加限制时经常使用）。在我看来 while 中的条件只是检查 bits 的符号，所以为什么要为他们使用的行烦恼呢？

public int nextInt(int bound) {
   if (bound <= 0)
        throw new IllegalArgumentException("bound must be positive");

      if ((bound & -bound) == bound)  // i.e., bound is a power of 2
        return (int)((bound * (long)next(31)) >> 31);

      int bits, val;
      do {
          bits = next(31);
          val = bits % bound;
      } while (bits - val + (bound-1) < 0);
      return val;
 }

Answer 1

请注意 bits - val + (bound-1) < 0 实际上是在检查 bits - val + (bound-1) 是否溢出 。 bits总是等于或大于val，而bound总是正数，所以正常情况下LHS没办法为正数。

我们可以将 < 0 视为 > Integer.MAX_VALUE。

让我们绘制一个 bits - val + (bound - 1) 的图表。我在 desmos here 上做了一个。假设 bound 是 100（小范围）：

x轴是bits，y轴是bits - val + (bound-1)，我在x轴和y轴上都加了线表示Integer.MAX_VALUE。请注意，bits 受 Integer.MAX_VALUE 限制。

在这个比例下，您可以看到 bits - val + (bound-1) 似乎永远不会溢出。如果将放大很多，您将看到：

请注意，bits < Integer.MAX_VALUE 的 bits 值范围很小，但 bits - val + (bound - 1) > Integer.MAX_VALUE.

对于 b = (1 << 30) + 1，图表如下所示：

任何大于 1 << 30 的 b 都会溢出。因此，如文档所述，有 1/2 的机会拒绝边界。

了解 Java 具有绑定算法的随机下一个整数

Understanding Java Random next Integer with bound algorithm

java

random

integer