如何有效地将几个字节转换为一个范围之间的整数？

我正在写一些读取字节的东西（只是一个List<int>）来自远程随机数生成源，速度非常慢。为此和我的个人要求，我想检索源中尽可能少的字节.

现在我正在尝试实现一种签名如下的方法：

int getRandomInteger(int min, int max)

我有两种理论如何从我的随机源中获取字节，并将它们转换为整数。

方法#1 很天真。拿来(max - min) / 256字节数并将它们相加。它可以工作，但是它将从我拥有的慢速随机数生成器源中获取大量字节。例如，如果我想获得一百万到零之间的随机整数，它将获取近 4000 字节......这是不可接受的。

方法#2 对我来说听起来很理想，但我无法想出算法。事情是这样的：

我们以 min: 0, max: 1000 为例。

• 计算ceil(rangeSize / 256)在这种情况下是ceil(1000 / 256) = 4。现在从源中获取一 (1) 个字节。
• 将这一字节从 0-255 范围缩放到 0-3 范围（或 1-4），并让它确定我们使用哪一组。例如。如果字节是 250，我们会选择第四组（代表最后 250 个数字，在我们的范围内 750-1000）。
• 现在获取另一个字节并从 0-255 到 0-250 进行调整，并让它确定我们在组中的位置。因此，如果第二个字节是例如120，那么我们最终的整数是750 + 120 = 870.

在这种情况下，我们总共只需要获取 2 个字节。然而，它要复杂得多，因为我们的范围是 0-1000000，我们需要几个“组”。

我该如何实现这样的事情？我可以接受 Java/C#/JavaScript 代码或伪代码。

我还想保持结果不丢失熵/随机性。所以，我有点担心缩放整数。

不幸的是，你的方法 #1 被破坏了。例如，如果最小值为 0，最大值为 510，则需要添加 2 个字节。只有一种方法可以获得 0 结果：两个字节都为零。出现这种情况的几率是 (1/256)^2。然而，有很多方法可以获取其他值，例如 100 = 100+0、99+1、98+2...因此 100 的机会要大得多：101(1/256)^2。

做你想做的事情的或多或少的标准方法是：

Let R = max - min + 1   -- the number of possible random output values
Let N = 2^k >= mR, m>=1  -- a power of 2 at least as big as some multiple of R that you choose.
loop
   b = a random integer in 0..N-1 formed from k random bits
while b >= mR -- reject b values that would bias the output
return min + floor(b/m)

这称为拒绝法。它丢弃随机选择的二进制数，这些二进制数会使输出产生偏差。如果min-max+1恰好是 2 的幂，那么你的拒绝率将为零。

如果你有m=1 and min-max+1只要比 2 的大幂多 1，那么拒绝率就会接近一半。在这种情况下，你肯定想要更大的m.

一般来说，较大的 m 值会导致较少的拒绝，但当然它们需要每个数字稍多的位数。有一个概率最优算法可供选择m.

这里提出的其他一些解决方案也有问题，但很抱歉，我现在没有时间发表评论。如果有兴趣的话也许过几天吧。