`rand.intn` 函数的内部工作原理 - GoLang

所以：

n % (1 << k)

和：

n & (1<
产生相同的结果。具体来说，当k==4时，这是n%16或n&0xf。当 k==5 时，这是 n%32 或 n&0x1f。尝试 k==0 和 k==63。
go 语言简介
我们现在准备考虑在 go 中完成所有这些工作。我们注意到 int （简单、朴实的 int）保证能够分别保存 -2147483648 和 +2147483647（-0x80000000 到 +0x7fffffff）之间的值。它可能一直延伸到-0x8000000000000000到+0x7ffffffffffffff。
同时，int32 始终处理较小的范围，int64 始终处理较大的范围。普通的 int 是与其他两者不同的类型，但实现相同的范围作为两者之一。我们只是不知道是哪一个。
我们的 int31 实现返回 0..0x7ffffff 范围内的均匀分布随机数。 （它通过返回 r.int63() 的高 32 位来实现这一点，尽管这是一个实现细节。）我们的 int63 实现返回 0..0x7fffffffffffff 范围内的均匀分布的随机数。
此处显示的 intn 函数：
func (r *rand) intn(n int) int {
    if n <= 0 {
        panic("invalid argument to intn")
    }
    if n <= 1<<31-1 {
        return int(r.int31n(int32(n)))
    }
    return int(r.int63n(int64(n)))
}

仅根据 n 的值选择两个函数之一：如果它小于或等于 0x7fffffff (1<<31 - 1)，则结果适合 int32，因此它使用 in t32(n) 将 n 转换为int32，调用r.int31n，并将结果转换回int。否则，n 的值超过 0x7fffffff，这意味着 int 具有更大的范围，我们必须使用更大范围的生成器 r.int63n。除了类型之外，其余部分相同。
代码可以执行以下操作：
return int(r.int63n(int64(n)))
每次，但在 32 位机器上，64 位算术可能很慢，这可能会很慢。 （这里有很多可能和可能，如果你今天自己写这篇文章，你应该从对代码进行分析/基准测试开始。go 作者做了 这样做，尽管这是很多年前的事了；在那个时候 做这些奇特的事情是值得的。）
更多位操作
函数 int31n 和 int63n 的内部非常相似；主要区别在于所涉及的类型，以及在一些地方的最大值。同样，造成这种情况的原因至少部分是历史性的：在某些（大多数是现在较旧的）计算机上，int63n 变体比 int32n 变体慢得多。 （在某些非 go 语言中，我们可能将它们编写为泛型，然后让编译器自动生成特定于类型的版本。）因此，让我们看看 int63 变体：
func (r *rand) int63n(n int64) int64 {
    if n <= 0 {
        panic("invalid argument to int63n")
    }
    if n&(n-1) == 0 { // n is power of two, can mask
        return r.int63() & (n - 1)
    }
    max := int64((1 << 63) - 1 - (1<<63)%uint64(n))
    v := r.int63()
    for v > max {
        v = r.int63()
    }
    return v % n
}

参数 n 的类型为 int64，因此其值不会超过 263-1 或 0x7ffffffffffffff 或 9223372036854775807。但它可能为负数，负值将无法正常工作，因此我们做的第一件事就是测试这一点，如果是的话就恐慌。如果输入为零，我们也会感到恐慌（这是一个选择，但现在记下它很有用）。
接下来我们进行 n&(n-1) == 0 测试。这是对 2 的幂的测试，有一个小缺陷，它适用于多种语言（具有位掩码的语言）：
在数字的二进制表示形式中，2 的幂始终表示为单个设置位。例如，2本身是000000012，4是000000102，8是000001002，依此类推，直到128是100000002。 （因为我只“绘制”了 8 位，所以该系列的最大位数为 128。）

从该数字中减去 1 会导致借位：该位变为零，所有较小的位都变为 1。例如，100000002 - 1 是 011111112.

如果最初只设置了单个位，则将这两个值进行“与”运算会产生零。如果不是，例如，如果我们最初的值是 130 或 100000102，减去 1 会得到 100000012 - top 位，因此最高位在两个输入中都被设置，因此在 and 运算结果中也被设置。

稍有缺陷的是，如果初始值为零，则我们有 0-1，它会产生全 1； 0&0xffffffffffffffff 也为零，但零不是 2 的整数次幂。 （20 是 1，而不是 0。）这个小缺陷对于我们的目的来说并不重要，因为我们已经确保对这种情况感到恐慌：它只是不会发生。
现在我们有了最复杂的一行：
    max := int64((1 << 63) - 1 - (1<<63)%uint64(n))

这里重复出现 63 是因为我们的值范围从 0 到 263-1。 1<<63 - 1 是（仍然、再次、始终）9223372036854775807 或 0x7fffffffffffffff。同时，1<<63，如果不减1，则为9223372036854775808或0x8000000000000000。 此值不适合 int64，但它确实适合 uint64。因此，如果我们将 n 转换为 uint64，我们可以计算 uint64(9223372036854775808) % uint64(n)，这就是 % 表达式的作用。通过使用 uint64 进行此计算，我们确保它不会溢出。
但是：这个计算到底是为了什么呢？好吧，回到我们的例子，使用 generate() 生成 [0..7] 中的值。当我们想要 [0..5] 中的数字时，我们必须丢弃 6 和 7。这就是我们在这里要做的：我们想要找到高于该值的值 >丢弃值。
如果我们取 8%6，我们会得到 2。8 比我们的 3 位 generate() 生成的最大值大 1。 8%6 == 2 是我们必须丢弃的“高值”的数量：8-2 = 6 并且我们要丢弃 6 或更多的值。减去 1，我们得到 7-2 = 5；我们可以接受此输入范围内的数字，从 0 到 5（含）。
因此，这种用于设置 max 的有点奇特的计算只是找出我们喜欢的最大值的一种方法。大于 max 的值需要被丢弃。
即使 n 远小于我们的生成器返回值，这种特殊的计算也能很好地工作。例如，假设我们有一个四位生成器，返回 [0..15] 范围内的值，并且我们想要 [0..2] 内的数字。因此，我们的 n 是 3（表示我们想要 [0..2] 中的数字）。我们计算 16%3 得到 1。然后我们取 15（比我们的最大输出值小一）- 1 得到 14 作为我们的最大可接受值。也就是说，我们允许 [0..14] 中的数字，但排除 15。
如果 63 位生成器返回 [0..9223372036854775807] 中的值，并且 n==3，我们会将 max 设置为 9223372036854775805。这就是我们想要的：它抛出两个偏置值 9223372036854775806 和 922337203685477 5807.
代码的其余部分只是这样做：
    v := r.Int63()
    for v > max {
        v = r.Int63()
    }
    return v % n

我们选择一个 int63 范围数字。如果它超过 max，我们选择另一个并再次检查，直到我们选择一个在 [0..max] 范围内的值，包括 max。
一旦我们得到一个在范围内的数字，我们就可以根据需要使用 % n 缩小范围。例如，如果范围是 [0..2]，我们使用 v % 3。如果 v 为（比如说）14，则 14%3 为 2。我们的实际最大值再次为 9223372036854775805，无论 v 是什么，在 0 和该值之间，v%3 都在 0 和 2 之间，并且保持均匀分布，没有轻微偏差为 0 和 1（9223372036854775806 将为我们提供一个额外的 0，而 9223372036854775807 将为我们提供一个额外的 1）。
（现在对 int32 和 32 和 1<<32 重复上述操作，以获取 int31 函数。）
以上就是《`rand.intn` 函数的内部工作原理 - GoLang》的详细内容，更多关于的资料请关注golang学习网公众号！