模数运算符与零(回复:arc4random_uniform 来源)
Modulus Operator vs Zero (re: arc4random_uniform source)
发现自己正在查看 arc4random_uniform 来源 (http://bxr.su/o/lib/libc/crypt/arc4random_uniform.c)
我的问题涉及以下行(评论是他们的原始评论):
/* 2**32 % x == (2**32 - x) % x */
min = -upper_bound % upper_bound;
现在,我不是数学天才,但肯定 -N%N 永远等于零。那为什么不直接写
min=0
请务必注意,我们在这里处理的是无符号整数 (uint32_t
),因此 -upper_bound
并不像您认为的那样。由于模环绕,它实际上是 2**32 - upper_bound
,其目的在上面的评论中有解释(即获得 2**32 % upper_bound
而不会溢出)。
示例:
#include <stdio.h>
#include <stdint.h>
int main()
{
uint32_t upper_bound = 42;
uint32_t min = -upper_bound % upper_bound;
printf("%u -> %u\n", upper_bound, min);
return 0;
}
给出:
42 -> 4
首先值得一提的是变量是 uint32_t
,因此是无符号的。那我们仔细看看:
-upper_bound % upper_bound = (-upper_bound) % upper_bound;
。这意味着 -upper_bound
实际上是 upper_bound
的 2 的补码。假设upper_bound=10
,那么-upper_bound
就是0xFFFFFFF6=246
。然后-upper_bound % upper_bound = 246%10 = 6
。你可以测试一下。
发现自己正在查看 arc4random_uniform 来源 (http://bxr.su/o/lib/libc/crypt/arc4random_uniform.c)
我的问题涉及以下行(评论是他们的原始评论):
/* 2**32 % x == (2**32 - x) % x */
min = -upper_bound % upper_bound;
现在,我不是数学天才,但肯定 -N%N 永远等于零。那为什么不直接写
min=0
请务必注意,我们在这里处理的是无符号整数 (uint32_t
),因此 -upper_bound
并不像您认为的那样。由于模环绕,它实际上是 2**32 - upper_bound
,其目的在上面的评论中有解释(即获得 2**32 % upper_bound
而不会溢出)。
示例:
#include <stdio.h>
#include <stdint.h>
int main()
{
uint32_t upper_bound = 42;
uint32_t min = -upper_bound % upper_bound;
printf("%u -> %u\n", upper_bound, min);
return 0;
}
给出:
42 -> 4
首先值得一提的是变量是 uint32_t
,因此是无符号的。那我们仔细看看:
-upper_bound % upper_bound = (-upper_bound) % upper_bound;
。这意味着 -upper_bound
实际上是 upper_bound
的 2 的补码。假设upper_bound=10
,那么-upper_bound
就是0xFFFFFFF6=246
。然后-upper_bound % upper_bound = 246%10 = 6
。你可以测试一下。