虽然有许多方法来找到一个整数或浮点数的下一个二次幂,但是对于找到一个数字的最接近的二次幂,可选择的方法并不多。
我已经实施了以下内容:
这应该适用于任何非负且小于ULLONG_MAX的浮点值。但这似乎不是最优的。有没有更好(更高效)的实现这个函数的方法?
编辑: @Eric 对于我的应用程序,如果v == 0,则得到0是可以接受的。但对于一些人来说,这可能是一个问题,因为0不是2的幂。
@Blixodus 谢谢你的答案,它指引我朝着正确的方向。我根据你的想法创建了以下函数:
我已经实施了以下内容:
template <typename T>
static constexpr T round_pow2(T v) {
if constexpr (std::is_floating_point_v<T>) {
auto high = static_cast<unsigned long>(std::ceil(v));
auto low = static_cast<unsigned long>(std::floor(v));
if (high == low) {
return round_pow2<unsigned long>(high);
} else {
T a = static_cast<T>(round_pow2<unsigned long>(low));
T b = static_cast<T>(round_pow2<unsigned long>(high));
return std::abs(a - v) <= std::abs(b - v) ? a : b;
}
} else {
T high = v - 1;
for (T i = 1; i < static_cast<T>(sizeof(T)); i *= 2) {
high |= high >> i;
}
high += 1;
T low = high >> 1;
return (high - v) < (v - low) ? high : low;
}
}
这应该适用于任何非负且小于ULLONG_MAX的浮点值。但这似乎不是最优的。有没有更好(更高效)的实现这个函数的方法?
编辑: @Eric 对于我的应用程序,如果v == 0,则得到0是可以接受的。但对于一些人来说,这可能是一个问题,因为0不是2的幂。
@Blixodus 谢谢你的答案,它指引我朝着正确的方向。我根据你的想法创建了以下函数:
template <typename T>
constexpr T round_p2(T v) {
if constexpr (std::is_floating_point_v<T>) {
using R = std::conditional_t<
std::is_same_v<T, double>, uint64_t,
std::conditional_t<std::is_same_v<T, float>, uint32_t,
void
>>;
auto [mlen, es, em] = std::is_same_v<T, double> ? std::make_tuple(52, 1024, 0x7FF) : std::make_tuple(23, 128, 0xFF);
auto y = *reinterpret_cast<R*>(&v);
return (T(y >> (sizeof(R) * 8 - 1)) * -2 + 1) * (2 << (((y >> mlen) & em) - es + ((y >> mlen - 1) & 0x1)));
} else {
using R = std::make_unsigned_t<T>;
R rv = static_cast<R>(v);
T sign = 1;
if constexpr (std::is_signed_v<T>) {
if (v < 0) {
rv = static_cast<R>(-v);
sign = -1;
}
}
R high = rv - 1;
for (R i = 1; i < static_cast<R>(sizeof(R)); i *= 2) {
high |= high >> i;
}
high += 1;
R low = high >> 1;
return sign * static_cast<T>((high - rv) <= (rv - low) ? high : low);
}
}
对于我的应用来说,它似乎运行得非常好,并且与我第一次实现相比,生成的汇编代码非常漂亮。
解释: 首先,根据v是浮点数还是双精度数,我获取三个魔术值:第一个是尾数的长度,第二个是指数需要减去的量(加一),第三个是用于从fp表示中提取指数的掩码。
然后,我将fp值转换为相同大小的无符号整数,以便能够对其进行操作。
接下来,我使用(T(y >> (sizeof(R) * 8 - 1)) * -2 + 1)
提取将签署最终结果的值。这会提取fp值的最高位(即符号位,正数为0,负数为1),然后将函数f(x) = x * -2 + 1
应用于它,这样当x=0
时,结果为1
,当x=1
时,结果为-1
。
std::pow
函数,而是使用位移(因为我们在处理二次幂)。我需要通过将我们要进行2位移的值减去1来考虑这一点(因此es
的值比预期多1)。
x ^ (x-1)
,我记不清了。不需要使用循环。 - user207421x ^ (x-1)
是用来找到最低有效位的。这对于找到最接近的二的幂是没有用的,因为它受到最高有效位的影响。 - Eric Postpischil