对数空间中一致生成随机整数

Question

我想要生成在对数空间中均匀分布的随机整数。也就是说，日志的值将均匀分布。

一个正常的均匀分布的无符号int将有75%的震级在10亿以上，大约在100万以上的99.98%，因此小的值被低估了。例如，来自日志空间的统一值的取值范围为4-8，与256-512相同。

现在，忽略负值，我能想到的一种方法是：

Random r = new Random();
return (int)Math.pow(2, r.nextDouble() * 31);

这应该会产生一个31位的日志均匀分布。但是，它不会很快，有一个pow()操作，并引入浮点值来生成整数，这有点难闻。此外，double的很多范围被Random.nextDouble()丢失了，我不清楚这段代码是否能够生成所有的2^31-1正整数值。

更好的解决方案欢迎。

下面有两种类似的解决方案，它们都涉及到用随机位填充整数，然后将随机数的位移到右边。类似于：

int number = rand.nextInt(Integer.MAX_VALUE) >> rand.nextInt(Integer.SIZE);

这有两种偏见：

分步偏倚

这会产生一种逐步分布的日志值，而不是平滑的值。特别是，在0,31中的随机值的右移，意味着整数有31个同样可能的“大小”，而在这个范围内的每一个值都是同样可能的。由于范围N中有2^N值，一个范围内的值是下一个范围中值的两倍--因此您可以在范围之间得到日志行为，但是范围本身是平坦的。

我不知道有什么简单的方法可以摆脱这种偏见。

顶位偏置

第二种形式的偏置发生，因为MSB并不总是1(例如，即使移位量为10，也不需要产生31-10=21位值，就会有额外的失真。实际上，范围是重叠的。值1不仅存在于移位量为30的情况下( p(1)=.5)，而且对于29 (p(1)=0.25)、28 (p(1)=.125)的位移也是如此。对于较小的值，这种效果会被抵消(也就是说，如果只看30和29的移位量，1似乎比2的可能性高3倍，而不是2倍的预测值，但一旦你看了更多的值，它就会收敛。)但是，对于较大的值，它不会抵消，这就是为什么您在@sprinter的答案中看到20:32207桶比其他桶小的原因。

我认为这种形式的偏见可以很容易地消除，只需将顶部比特强制为零，所以类似于：

(r.nextInt(0x40000000) | 0x40000000) >> r.nextInt(31)

这还有一些其他的调整-- rand的最大值为2^30，这更快(对于nextInt(int)代码中2的幂的特殊情况)，因为我们永远不希望设置第二个从MSB位(我们强制它到1)。这也消除了一个微观的额外的偏差来源，即永远无法生成Integer.MAX_VALUE，因此在完全表示中缺少一个值。

它移位[0，31]位，所以你永远不会得到零，如果你也想要零，把它改变为[0,32)位，你会得到零的频率相等于1(技术上不再是日志分布的，但在很多情况下有用)。另一种方法是从最终值中减去一个，得到零(代价是永远得不到Integer.MAX_VALUE)。

Answer 1

不正确的答案只提供信息。由于问题中给出的原因，不满足OP的要求。

int number = rand.nextInt(Integer.MAX_VALUE) >> rand.nextInt(Integer.SIZE);

我对此的非正式测试似乎表明存在预期的偏差。我以这种方式生成了1万个数字，并有以下日志分布(忽略零)

0:46819
1:47045
2:40663
3:44001
4:45306
5:43802
6:46447
7:43355
8:47366
9:42747
10:46387
11:43899
12:45179
13:45496
14:44431
15:46751
16:43055
17:47127
18:41243
19:41837
20:32207
21:11965