kus*_*lvm 0 bit-manipulation go random-seed
不知何故，我碰巧查看了 Go 的源代码，了解它如何在传递数组长度时实现 Random 函数。
这是调用代码
func randomFormat() string {
formats := []string{
"Hi, %v. Welcome!",
"Great to see you, %v!",
"Hail, %v! Well met!",
}
return formats[rand.Intn(len(formats))]
}
Go源代码：主要部分
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)))
}
Go 源代码：参考部分 - 大多数开发人员已经将其安装在他们的机器或 go 存储库上。
// Int31n returns, as an int32, a non-negative pseudo-random number in [0,n).
// It panics if n <= 0.
func (r *Rand) Int31n(n int32) int32 {
if n <= 0 {
panic("invalid argument to Int31n")
}
if n&(n-1) == 0 { // n is power of two, can mask
return r.Int31() & (n - 1)
}
max := int32((1 << 31) - 1 - (1<<31)%uint32(n))
v := r.Int31()
for v > max {
v = r.Int31()
}
return v % n
}
// It panics if n <= 0.
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
}
func (r *Rand) Int31() int32 { return int32(r.Int63() >> 32) }
func (r *Rand) Int63() int64 { return r.src.Int63() }
type Source interface {
Int63() int64
Seed(seed int64)
}
我想了解随机函数如何封装所有内部函数。我对代码感到不知所措，如果有人必须用简单的英语来计划步骤，那会是什么？
例如，我不明白在中执行负 1 的逻辑
if n <= 1<<31-1
然后，我没有得到任何Int31n功能
if n&(n-1) == 0 { // n is power of two, can mask
return r.Int31() & (n - 1)
}
max := int32((1 << 31) - 1 - (1<<31)%uint32(n))
v := r.Int31()
for v > max {
v = r.Int31()
}
return v % n
这更多是一个关于算法的问题，而不是关于 Go 的问题，但是有一些 Go 的部分。无论如何，我将从算法问题开始。
\n假设我们有一个均匀分布随机数生成器，它返回一个介于 0 和 7 之间的数字（包括 0 和 7）。也就是说，随着时间的推移，它将返回大约相同数量的 0、1、2、...、7，但它们之间没有明显的模式。
\n现在，如果我们想要一个 0 到 7 之间均匀分布的随机数，这个东西就完美了。这就是它返回的内容。我们只是使用它。但是如果我们想要一个 0 到 6 之间均匀分布的随机数呢？
\n我们可以写：
\nfunc randMod7() int {\n return generate() % 7\n}\n因此，如果generate()返回 7（有八分之一的机会这样做），我们将该值转换为零。但是这样我们就会在 8 次中得到 2 次归零，而不是在 8 次中得到 1 次。平均而言，我们将在 8 次中得到 1、2、3、4、5 和 6，并在 8 次中得到 2 次：每个实际 0 一次，每个 7 一次。
那么，我们需要做的是丢弃任何出现的 7：
\nfunc randMod7() int {\n for {\n if i := generate() < 7 {\n return i\n }\n // oops, got 7, try again\n }\n}\n现在，如果我们有一个名为的统一随机数生成器，generate()它返回一个介于 0 到 11（12 个可能值）之间的值，并且我们想要一个介于 0 到 3 之间的值（四个可能值），我们可以使用generate() % 4因为 12 个可能的结果将以相同的概率分为 3 组，每组 4 个。如果我们想要一个介于 0 和 5 之间的值（含 0 和 5），我们可以使用generate() % 6，因为 12 个可能的结果将以相同的概率分为两组，每组 6 个。事实上，我们需要做的就是检查统一数生成器范围的质因数分解，看看哪些模起作用。12的因数是2、2、3；所以 2、3、4 和 6 都在这里工作。任何其他模数（例如 ）generate() % 10都会产生有偏差的结果：0 和 1 在 12 次中出现 2 次，但 2 到 9 在 12 次中出现 1 次。（注意：generate() % 12也可以，但有点毫无意义。）
在我们的特定情况下，我们有两个不同的均匀随机数生成器可用。一、Int31()生成 0 到 0x7fffffff（十进制 2147483647，或 2 31 - 1，或1<<31 - 1）之间的值（包括 0 和 0x7fffffff）。另一个 ,Int63()生成 0 到 0x7fffffffffffffff 之间的值（9223372036854775807 或 2 63 - 1 或1<<63 - 1）。这些范围包含 2 31和 2 63值，因此它们的素因数分解为 31 个 2 或 63 个 2。
这意味着我们可以计算0 到 31 之间的任何整数的Int31()mod 2 ，而不会破坏我们的均匀性。使用，我们可以做同样的事情，范围一直到 63。kkInt63()k
现在，从数学和计算机角度来说，给定[ .. ] 或 [ .. ] 中的任何非负整数n，以及正确范围内的非负整数k（分别不超过 31 或 63），计算：整数n mod 2 k产生的结果与计算该整数并使用k位集执行位掩码操作相同。为了获得设置的位数，我们需要减去1。如果是，比如说 4，我们得到 1<<4 或 16。减去 1，我们得到 15 或 0xf，其中有四个 1 位。00x7ffffff00x7fffffffffffffff1<<kk
所以：
\nn % (1 << k)\n和：
\nn & (1<<k - 1)\n产生相同的结果。具体来说，当 时k==4，这是n%16或n&0xf。当k==5这是n%32或 时n&0x1f。尝试一下k==0和k==63。
我们现在准备考虑在 Go 中完成所有这些工作。我们注意到int(plain, unadorned int) 保证能够分别保存 -2147483648 和 +2147483647（-0x80000000 到 +0x7fffffff）之间的值。它可以一直延伸到 -0x8000000000000000 到 +0x7ffffffffffffff。
同时，int32始终处理较小的范围并int64始终处理较大的范围。普通类型与其他两种类型int不同，但实现与两者之一相同的范围。我们只是不知道是哪一个。
我们的Int31实现返回一个范围内均匀分布的随机数0..0x7ffffff。（它通过返回 的高 32 位来实现这一点r.Int63()，尽管这是一个实现细节。）我们的Int63实现返回一个均匀分布的随机数0..0x7ffffffffffffff。
这Intn您在此处显示的功能
func randMod7() int {\n return generate() % 7\n}\n只是根据 的值选择两个函数之一n：如果它小于或等于0x7fffffff( 1<<31 - 1)，则结果适合int32，因此它使用int32(n)转换n为int32，调用r.Int31n，并将结果转换回int。否则， 的值n超过0x7fffffff，这意味着int具有更大的范围，我们必须使用更大范围的生成器，r.Int63n。除了类型之外，其余都是相同的。
代码可以这样做：
\nreturn int(r.Int63n(int64(n)))\n每次，但在 32 位机器上，64 位算术可能很慢，这可能会很慢。（这里有很多可能和可能，如果你今天自己写这篇文章，你应该从对代码进行分析/基准测试开始。Go 作者确实这样做了，尽管这是很多年前的事了；当时这是值得的做这些奇特的事情。）
\nInt31n两者的功能和内部结构Int63n非常相似；主要区别在于所涉及的类型，以及在一些地方的最大值。同样，造成这种情况的原因至少部分是历史性的：在某些（现在大多是旧的）计算机上，该Int63n变体比该变体慢得多Int32n。（在某些非 Go 语言中，我们可能将它们编写为泛型，然后让编译器自动生成特定于类型的版本。）所以让我们看看变Int63体：
func randMod7() int {\n for {\n if i := generate() < 7 {\n return i\n }\n // oops, got 7, try again\n }\n}\n参数n的类型为int64，因此它的值不会超过 2 63 -1 或0x7fffffffffffffff或 9223372036854775807。但它可能是负数，并且负值将无法正常工作，因此我们要做的第一件事就是测试它，如果是，则恐慌。如果输入为零，我们也会感到恐慌（这是一个选择，但现在记下它很有用）。
接下来我们进行测试n&(n-1) == 0。这是对 2 的幂的测试，有一个小缺陷，它适用于多种语言（具有位掩码的语言）：
在数字的二进制表示中，2 的幂始终表示为单个设置位。例如，2 本身是 00000001 2，4 是 00000010 2，8 是 00000100 2，依此类推，直到 128 是 10000000 2。（因为我只“画”了 8 位，所以这个系列的最大值为 128。）
\n从该数字中减去 1 会导致借位：该位变为零，所有较小的位都变为 1。例如， 10000000 2 - 1 是 01111111 2。
\n如果最初只设置了单个位，则将这两个值进行“与”运算会产生零。如果不是\xe2\x80\x94，例如，如果我们最初的值为 130 或 10000010 2，减去 1 得到 10000001 2 \xe2\x80\x94，则顶部没有借位，因此最高位设置为两个输入，因此在“与”结果中设置。
\n轻微的缺陷是，如果初始值为零，那么我们有0-1，它会产生全 1；0&0xffffffffffffffff也为零，但零不是二的整数次方。（2 0是 1，而不是 0。）这个小缺陷对于我们的目的来说并不重要，因为我们已经确保对这种情况感到恐慌：它只是不会发生。
现在我们有了最复杂的一行：
\nn % (1 << k)\n这里重复出现63s 是因为我们的值范围是从 0 到 2 63 -1。 1<<63 - 1是（仍然，再次，总是）9223372036854775807 或0x7fffffffffffffff. 同时，1<<63不减 1 则为 9223372036854775808 或0x8000000000000000。 该值不适合int64，但适合uint64。因此，如果我们变成na uint64，我们就可以计算uint64(9223372036854775808) % uint64(n)，这就是%表达式的作用。通过用于uint64此计算，我们确保它不会溢出。
但是：这个计算到底是为了什么呢？好吧，回到我们的例子，agenerate()产生 [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 和 92233720368547758 07.
\n代码的其余部分只是这样做：
\nn & (1<<k - 1)\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）。
（现在对函数重复上面的int32and32和, 。）1<<32Int31
| 归档时间： |
|
| 查看次数： |
1500 次 |
| 最近记录： |