在rand()中使用位移位以允许更大的随机范围
我正在检查一个函数以生成基映射的键，并发现rand()的实现对我来说很新奇。
以下是功能：
static int make_random(RadixMap *map)
{
size_t i = 0;
for (i = 0; i < map->max - 1; i++){
uint32_t key = (uint32_t) (rand() | (rand() << 16));<--This was interesting
check(RadixMap_add(map, key, i) == 0, "Failed to add key %u", key);
}
return i;
error:
return 0;
}
----- Type definitions --------
typedef union RMElement {
uint64_t raw;
struct {
uint32_t key;
uint32_t value;
} data;
} RMElement;
typedef struct RadixMap {
size_t max;
size_t end;
uint32_t counter;
RMElement *contents;
RMElement *temp;
} RadixMap;从ex35学习C-- Zed的艰难之路
我发现最有趣的部分是
uint32_t key = (uint32_t) (rand() | (rand() << 16)); <-- This was interesting这对我来说很有趣，因为这样做是可能的。
uint32_t key = rand();由于RAND_MAX (0x7FFFFFFF)小于uint32_t MAX (0xFFFFFF)
位移位实现看起来有以下优点。
- 允许较大的随机值范围，0xFFFFFFF与0x7FFFFFF
- 值(初始0除外)至少是5位小数(65537) (0x10001)
- 减少看到"0“的概率。
和下面的缺点
- 增加了代码复杂度？
使用这个rand()的位移位实现还有其他原因吗？
我一直试图找出在代码评审中使用此实现的原因，并希望确保我的思路正确。
回答 3
Stack Overflow用户
发布于 2021-04-27 01:39:29
C标准只保证RAND_MAX至少为32767。这段代码通过两次调用rand并移动以确保它至少具有30位的随机性来解释这一点。
然而，这并不能恰当地解释RAND_MAX更大的情况。
rand函数返回一个已签名的int。如果RAND_MAX与INT_MAX相同，rand() << 16很可能将"1“位转换为符号位，从而触发未定义行为。
为处理这两种情况，实现这一目标的适当方法是：
uint32_t key = rand() | ((uint32_t)rand() << 16));因为左移位，所以只要移位量小于类型的大小，就可以很好地定义一个无符号数字。
或者更好的是：
uint32_t key = (((uint32_t)rand() & 0x7FFF) << 17) |
(((uint32_t)rand() & 0x7FFF) << 2) |
((uint32_t)rand() & 0x3);才能得到完整的32位随机性。
Stack Overflow用户
发布于 2021-04-27 01:44:59
uint32_t key = (uint32_t) (rand() | (rand() << 16));也有缺点。
- 当
RAND_MAX != 65535不均匀时，这是通常的情况。 - 当
int为16位时，未定义的行为。另外，由于有符号整数溢出的可能性，在其他情况下也使用rand() << 16。 - 演员阵容太晚了，无法抵御狭窄的
int。实际上，与uint32_t key = rand() | (rand() << 16);uint32_t key = rand() + (rand() * (RAND_MAX+(uint32_t key)1);一样，更有意义。
一个关键的缺点是使用|来追加右边的零位与RAND_MAX的位宽不一样。
第二个弱点是假设转移比乘以2的力量要好。无论哪种方式，一个好的编译器都能发出高效的代码。
相反，根据需要根据RAND_MAX调用随机函数(1次、2次或3次)。当RAND_MAX是一个Mersenne数时，下面的效果很好。
#define IMAX_BITS(m) ((m)/((m)%255+1) / 255%255*8 + 7-86/((m)%255+12))
// Bit width of RAND_MAX, which is at least 15
#define RAND_MAX_BITS IMAX_BITS(RAND_MAX)
_Static_assert(((RAND_MAX + 1u) & RAND_MAX) == 0, "RAND_MAX is not a Mersenne number");
uint32_t rand32(void) {
uint32_t r = rand();
#if RAND_MAX_BITS < 32
r = (r << RAND_MAX_BITS) | rand();
#endif
#if RAND_MAX_BITS*2 < 32
r = (r << RAND_MAX_BITS) | rand();
#endif
return r;
}(位移位)增加了代码复杂度？
不是的。
使用这个rand()的位移位实现还有其他原因吗？
OP的代码并不是统一的，因为它通常倾向于一个比特，因为它的潜力或者十五号以后的位数。
我一直在努力找出使用这个实现的原因.
不要用它。
Stack Overflow用户
发布于 2021-04-27 04:35:09
或者，你可以用一个非常快的随机数发生器。注意，没有看到没有太多零字节的值。
uint64_t
xorshift128plus(uint64_t seed[2])
{
uint64_t x = seed[0];
uint64_t y = seed[1];
seed[0] = y;
x ^= x << 23;
seed[1] = x ^ y ^ (x >> 17) ^ (y >> 26);
return s[1] + y;
}将结果转换为浮动或调制最大int值.
https://stackoverflow.com/questions/67275561
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号