在 log space 中均匀生成随机整数
Generating random integers uniformly in log space
我想生成在 log space 中均匀分布的随机整数。即 的值的对数将均匀分布。
一个正常的均匀分布的 unsigned int 将有 75% 的大小超过 10 亿，大约 99.98% 的大小超过 100 万，因此小值的代表性不足。来自 log space 的统一值将在 4-8 范围内具有相同数量的值，例如 256-512。
暂时忽略负值，我能想到的一种方法是：
Random r = new Random();
return (int)Math.pow(2, r.nextDouble() * 31);
那应该生成一个31位的log-uniformly distributed。虽然它不会很快，但其中有一个 pow() 操作并引入浮点值来生成整数有点难闻。此外，double 的很多范围都被 Random.nextDouble() 丢失了，我不清楚这段代码是否可以生成所有 2^31-1 正整数值。
欢迎更好的解决方案。
下面有两个类似的解决方案，都涉及用随机位填充整数，然后向右移动随机数位。类似于：
int number = rand.nextInt(Integer.MAX_VALUE) >> rand.nextInt(Integer.SIZE);
这有两种偏差：
逐步偏差
这会产生一种逐步对数分布值，而不是平滑分布值。特别是，在 [0,31] 中右移一个随机值，意味着有 31 个等概率的 "sizes" 整数，并且该范围内的每个值都是等概率的。由于 N 范围内有 2^N 个值，一个范围内的值的概率是下一个范围内值的两倍 - 因此您在范围之间获得对数行为，但范围本身是平坦的。
我不知道有什么简单的方法可以消除这种偏见。
最高位偏差
第二种形式的偏差发生是因为 MSB 并不总是 1（例如，即使移位量为 10，也不一定会产生 31-10=21 位值，存在额外的失真。实际上, 范围重叠。对于 30 的移位量，值 1 不仅存在（p(1)=.5），而且对于 29 (p(1)=0.25)、28 (p(1) =.125)，依此类推。该效应抵消了较小的值（即，如果您仅查看 30 和 29 的移位量，1 似乎比 2 的可能性高 3 倍，而不是预测值 2 倍，但是一旦你看到更多的值，它就会收敛。然而，它不会抵消大的值，这就是为什么你看到 20:32207 桶比@sprinter 的答案中的其他桶小。
我认为这种形式的偏见可以很容易地通过强制最高位为零来消除，所以像这样：
(r.nextInt(0x40000000) | 0x40000000) >> r.nextInt(31)
这还有其他一些调整 - rand 最大为 2^30，速度更快（nextInt(int) 代码中 2 的幂的特殊情况），因为我们不想要第二个-无论如何设置 from-MSB 位（我们强制它为 1）。这也消除了一个微观的额外偏差来源，即永远无法生成 Integer.MAX_VALUE，因此完整表示中缺少一个值。
它移动 [0,31) 位，所以你永远不会得到零，如果你也想要零，将其更改为移动 [0,32) 位，你会得到频率等于 1 的零（技术上不再是日志分布的，但在许多情况下很有用）。另一种方法是从最终值中减去一个以获得零（以永远不会得到 Integer.MAX_VALUE 为代价）。
提供的错误答案仅供参考。由于问题中给出的原因，这不满足 OP 的要求。
int number = rand.nextInt(Integer.MAX_VALUE) >> rand.nextInt(Integer.SIZE);
我对此的非正式测试似乎表明存在预期的偏差。我以这种方式生成了 100 万个数字，并具有以下日志分布（忽略零）
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
我想生成在 log space 中均匀分布的随机整数。即 的值的对数将均匀分布。
一个正常的均匀分布的 unsigned int 将有 75% 的大小超过 10 亿，大约 99.98% 的大小超过 100 万，因此小值的代表性不足。来自 log space 的统一值将在 4-8 范围内具有相同数量的值，例如 256-512。
暂时忽略负值，我能想到的一种方法是：
Random r = new Random();
return (int)Math.pow(2, r.nextDouble() * 31);
那应该生成一个31位的log-uniformly distributed。虽然它不会很快，但其中有一个 pow() 操作并引入浮点值来生成整数有点难闻。此外，double 的很多范围都被 Random.nextDouble() 丢失了，我不清楚这段代码是否可以生成所有 2^31-1 正整数值。
欢迎更好的解决方案。
下面有两个类似的解决方案，都涉及用随机位填充整数，然后向右移动随机数位。类似于：
int number = rand.nextInt(Integer.MAX_VALUE) >> rand.nextInt(Integer.SIZE);
这有两种偏差：
逐步偏差
这会产生一种逐步对数分布值，而不是平滑分布值。特别是，在 [0,31] 中右移一个随机值，意味着有 31 个等概率的 "sizes" 整数，并且该范围内的每个值都是等概率的。由于 N 范围内有 2^N 个值，一个范围内的值的概率是下一个范围内值的两倍 - 因此您在范围之间获得对数行为，但范围本身是平坦的。
我不知道有什么简单的方法可以消除这种偏见。
最高位偏差
第二种形式的偏差发生是因为 MSB 并不总是 1（例如，即使移位量为 10，也不一定会产生 31-10=21 位值，存在额外的失真。实际上, 范围重叠。对于 30 的移位量，值 1 不仅存在（p(1)=.5），而且对于 29 (p(1)=0.25)、28 (p(1) =.125)，依此类推。该效应抵消了较小的值（即，如果您仅查看 30 和 29 的移位量，1 似乎比 2 的可能性高 3 倍，而不是预测值 2 倍，但是一旦你看到更多的值，它就会收敛。然而，它不会抵消大的值，这就是为什么你看到 20:32207 桶比@sprinter 的答案中的其他桶小。
我认为这种形式的偏见可以很容易地通过强制最高位为零来消除，所以像这样：
(r.nextInt(0x40000000) | 0x40000000) >> r.nextInt(31)
这还有其他一些调整 - rand 最大为 2^30，速度更快（nextInt(int) 代码中 2 的幂的特殊情况），因为我们不想要第二个-无论如何设置 from-MSB 位（我们强制它为 1）。这也消除了一个微观的额外偏差来源，即永远无法生成 Integer.MAX_VALUE，因此完整表示中缺少一个值。
它移动 [0,31) 位，所以你永远不会得到零，如果你也想要零，将其更改为移动 [0,32) 位，你会得到频率等于 1 的零（技术上不再是日志分布的，但在许多情况下很有用）。另一种方法是从最终值中减去一个以获得零（以永远不会得到 Integer.MAX_VALUE 为代价）。
提供的错误答案仅供参考。由于问题中给出的原因，这不满足 OP 的要求。
int number = rand.nextInt(Integer.MAX_VALUE) >> rand.nextInt(Integer.SIZE);
我对此的非正式测试似乎表明存在预期的偏差。我以这种方式生成了 100 万个数字，并具有以下日志分布（忽略零）
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