时间戳

首页 > 解决方案 > 将随机整数转换为范围 [min,max] 而不进行分支

c++ - 将随机整数转换为范围 [min,max] 而不进行分支

问题描述

我掌握了一个 SUPER-FAST 算法，它统一地生成一个随机字节数组。它比标准库的 c++ 均匀分布和 mersenne-twister 快 6 倍。

数组的计数可以被 4 整除，因此可以将其解释为整数数组。将每个条目转换为整数，会产生 range 中的值[INT_MIN, INT_MAX]。但是如何将这些整数值转换为介于我自己的值之间[min, maximum]？

我想避免任何 if-else，以避免分支。

也许我应该应用一些按位逻辑来丢弃每个数字中不相关的位？（因为所有剩余的未屏蔽位无论如何都是 0 或 1）。如果我可以提取最大值中的最高有效位，我可以在我的整数中屏蔽任何比该位更重要的位。

例如，如果我希望我max是 17 岁，那么它是00010001二进制形式。也许我的面具会看起来像00011111？然后我可以将它应用于我数组中的所有数字。

但是，这个掩码是错误的......它实际上允许值高达(1+2+4+8+16):(

我能做些什么？还有，怎么保养min？

编辑

我的应用程序的每一帧都为神经网络生成数百万个数字。我设法使用 AXV2 对浮点变量的代码进行矢量化（使用这篇文章），但也需要让整数工作。

标签： c++bit-manipulationsimdavx2

解决方案

但是如何将这些整数值转换为介于我自己的值之间[min, maximum]？

由于范围可能不是 2 的幂，因此位掩码已失效，但您已经发现了这一点。

Modulo 也出来了，它在 AVX2 中不作为本机操作存在（即使它存在，也不一定会使其高效）。

还有另一种选择：乘高，使用_mm256_mul_epu32（不幸的是，对于 32 位数字没有“纯”乘高，就像 16 位数字一样，所以我们被困在一个只做 50% 有用工作的操作上）。想法是获取输入数字x（全范围）和所需范围r，然后计算r * x / 2^32除法是隐式的（通过取乘积的高半部分来实现）。

x / 2^32如果将其解释为有理数，则将是 [0.0 .. 1.0) （不包括 1.0）中的数字，乘以rthen 会将范围扩展为 [0.0 .. r）（不包括r）。这不是它的计算方式，但这就是公式的来源。

min通过添加到缩放结果可以轻松设置范围的最小值。

在代码中（经过轻微测试）：

__m256i squish(__m256i x, int min, int max) {
    __m256i sizeOfRange = _mm256_set1_epi32((unsigned)max - min);
    __m256i scaled_even = _mm256_shuffle_epi32(_mm256_mul_epu32(x, sizeOfRange), 0xB1);
    __m256i scaled_odd = _mm256_mul_epu32(_mm256_shuffle_epi32(x, 0xB1), sizeOfRange);
    __m256i scaled = _mm256_blend_epi32(scaled_even, scaled_odd, 0xAA);
    return _mm256_add_epi32(scaled, _mm256_set1_epi32(min));
}

它仍然是一个专有范围，它无法处理完整[INT_MIN .. INT_MAX]的输出范围。甚至没有办法指定它，它最多可以做的是[INT_MIN .. INT_MAX)（或者例如具有零偏移量的等效范围：）[0 .. -1)。

它也不是真正均匀的，出于同样的原因，简单的基于模的范围缩小并不是真正均匀的，除非碰巧均匀地划分，否则你不能公平地将N弹珠划分到K垃圾箱上。KN

推荐阅读