编译时可以平方而不溢出的最大值是什么(整型)?

Question

在c++中，是否有一种编译时的方法来计算可以安全地平方的整型T的最大值，即在数学上x * x <= std::numeric_limits<T>::max()，以便如果要执行x*x操作，它不会导致未定义的行为(对于有符号类型)或溢出(对于无符号类型)?

我很好地限制只有在std::numeric_limits中有专门化的整型，即不需要担心新的用户定义的整型，如果这使它更容易。

当然，数学上的答案是floor(sqrt(std::numeric_limits<T>::max()))。例如，对于64位带符号的long long，这将是floor(sqrt(2^63-1)) == 3037000499。一个(即使对于大数也是正确的)constexpr sqrt可以做到这一点，尽管我不知道这是否是最好的方法。

答案应该是:

• 64位unsigned:floor(sqrt(2^64-1)) == 4294967295
• 64位符号:floor(sqrt(2^63-1)) == 3037000499
• 32位unsigned:floor(sqrt(2^32-1)) == 65535
• 32位符号:floor(sqrt(2^31-1)) == 46340

Answer 1

• 设置位的下半部分
• 对于签名类型，加1，然后除以sqrt(2)

#include <climits>
#include <limits>
#include <type_traits>
template<class T>
constexpr T largest_squareable() {
static_assert(std::is_integral_v<T>, "Must be an integral type");
if constexpr (std::is_unsigned_v<T>) {
return std::numeric_limits<T>::max() >> sizeof(T) * CHAR_BIT / 2;
} else {        
constexpr long double sqrt_2 = 1.41421356237309504880L;
return (largest_squareable<std::make_unsigned_t<T>>() + 1) / sqrt_2;    
}
}

演示或者直接手工定义值，因为大小的数量非常有限:

#include <cstdint>
template<typename T>
constexpr T largest_squareable();
template<> constexpr int8_t largest_squareable<int8_t>() { return 11; }
template<> constexpr uint8_t largest_squareable<uint8_t>() { return 15; }
template<> constexpr int16_t largest_squareable<int16_t>() { return 181; }
template<> constexpr uint16_t largest_squareable<uint16_t>() { return 255; }
template<> constexpr int32_t largest_squareable<int32_t>() { return 46340L; }
template<> constexpr uint32_t largest_squareable<uint32_t>() { return 65535UL; }
template<> constexpr int64_t largest_squareable<int64_t>() { return 3037000499LL; }
template<> constexpr uint64_t largest_squareable<uint64_t>() { return 4294967295ULL; }