时间戳

首页 > 解决方案 > 使用带有 rand() 的位移来允许更大的随机范围

c - 使用带有 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;

来自 Zed Shaw 的 ex35 Learn C the Hard Way

我发现有趣的具体部分是

uint32_t key = (uint32_t) (rand() | (rand() << 16)); <-- This was interesting

这对我来说很有趣，因为它本来可以简单地做 ..

uint32_t key = rand();

由于 RAND_MAX (0x7FFFFFFF) 小于 uint32_t MAX (0xFFFFFFFF)

移位实现看起来具有以下优点。

  1. 允许更大的随机值范围，0xFFFFFFFF 与 0x7FFFFFFF
  2. 值（初始 0 除外）至少为 5 位十进制 (65537) (0x10001)
  3. 减少看到“0”的概率。

以及以下缺点

  1. 增加代码复杂度？

使用 rand() 的这种位移实现还有其他原因吗？

我一直试图在我的代码审查中找出使用这个实现的原因，并想确保我的想法是正确的。

标签： c

解决方案

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 位随机性。

推荐阅读