虽然对于如何找到整数或浮点数的下一个2的幂的问题有很多答案,但是对于找到一个数字的最接近的2的幂却没有那么多答案。
我已经实现了以下内容:
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 fp值的情况。但这似乎不是最佳的。是否有更好(更高性能)的方法来实现此功能?
编辑:@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是float还是double:第一个是尾数的长度,第二个是指数需要递减(加1)的量,第三个是用于从FP表示中提取指数的掩码。
然后,我将fp值转换为相同大小的无符号整数,以便能够处理它。
接下来,我提取将使用(T(y >> (sizeof(R) * 8 - 1)) * -2 + 1)
对最终结果进行签名的值。它提取fp值的最高位(符号,0表示正,1表示负),然后将函数f(x) = x * -2 + 1
应用于它,这将为x=0
提供1
,为x=1
提供-1
。
最后,我使用Blixodus公式计算给定fp值的最接近的2的无符号幂。因为我不使用std::pow
函数来支持位移位(因为我们使用的是2的幂)。我需要通过将1移到我们移动2的值来解决这个问题(因此es
的值比预期的多1)。
2条答案
按热度按时间vyu0f0g11#
在C++ 2020之前,没有实现将整数舍入到2的幂,而不使用循环,编译器扩展或移位,假定对类型的宽度有一些限制。有几个关于堆栈溢出的问题。下面的代码显示了一个使用C++
std::countl_zero
的解决方案和一个使用GCC的count-leading-zeros内置的替代解决方案,该解决方案适用于unsigned long long
以下的任何整数类型。6qftjkof2#
浮点使用1位用于符号、n位用于指数和m位用于有效数来编码。例如,32位浮点数被编码为1位用于符号,8位用于指数,23位用于有效数。然后,32位浮点数的值由以下等式简单地给出
值=(-1)^sign * 2^(E-127)(1 + sum from i = 1 to 23(B_(23-1) 2^(-i)))
参见符号here
因此,如果有效数部分< 1.5,则更接近(-1)^sign2^(E-127),如果有效数部分>= 1.5,则更接近(-1)^sign2^(E-126)
有效数部分的第一位表示有效数是否< 1.5 or significand >为1.5(它将2^(-1)= 0.5加到总和上)
因此,您可以简单地查看有效数部分的第一位(在32位情况下为位数22),如果该位为0,则值更接近(-1)^sign2^(E-127),如果该位为1,则值更接近(-1)^sign2^(E-126)