What's the best C++ way to multiply unsigned integers modularly safely?
Some template metaprogramming with SFINAE, perhaps.
#include <type_traits>
template <typename T, typename std::enable_if<std::is_unsigned<T>::value && (sizeof(T) <= sizeof(unsigned int)) , int>::type = 0>
T safe_multiply(T a, T b) {
return (unsigned int)a * (unsigned int)b;
}
template <typename T, typename std::enable_if<std::is_unsigned<T>::value && (sizeof(T) > sizeof(unsigned int)) , int>::type = 0>
T safe_multiply(T a, T b) {
return a * b;
}
Demo.
Edit: simpler:
template <typename T, typename std::enable_if<std::is_unsigned<T>::value, int>::type = 0>
T safe_multiply(T a, T b) {
typedef typename std::make_unsigned<decltype(+a)>::type typ;
return (typ)a * (typ)b;
}
Demo.
Here's a relatively simple solution, which forces a promotion to unsigned int
instead of int
for unsigned type narrower than an int
. I don't think any code is generated by promote
, or at least no more code than the standard integer promotion; it will just force multiplication etc. to use unsigned ops instead of signed ones:
#include <type_traits>
// Promote to unsigned if standard arithmetic promotion loses unsignedness
template<typename integer>
using promoted =
typename std::conditional<std::numeric_limits<decltype(integer() + 0)>::is_signed,
unsigned,
integer>::type;
// function for template deduction
template<typename integer>
constexpr promoted<integer> promote(integer x) { return x; }
// Quick test
#include <cstdint>
#include <iostream>
#include <limits>
int main() {
uint8_t i8 = std::numeric_limits<uint8_t>::max();
uint16_t i16 = std::numeric_limits<uint16_t>::max();
uint32_t i32 = std::numeric_limits<uint32_t>::max();
uint64_t i64 = std::numeric_limits<uint64_t>::max();
i8 *= promote(i8);
i16 *= promote(i16);
i32 *= promote(i32);
i64 *= promote(i64);
std::cout << " 8: " << static_cast<int>(i8) << std::endl
<< "16: " << i16 << std::endl
<< "32: " << i32 << std::endl
<< "64: " << i64 << std::endl;
return 0;
}
This article regarding a C solution to the case of uint32_t * uint32_t
multiplication on a system in which int
is 64 bits has a really simple solution that I hadn't thought of: 32 bit unsigned multiply on 64 bit causing undefined behavior?
That solution, translated to my problem, is simple:
// C++
static_cast<std::uint16_t>(1U * x * x)
// C
(uint16_t) (1U * x * x)
Simply involving 1U
in the left side of the chain of arithmetic operations like that will promote the first parameter to the larger rank of unsigned int
and std::uint16_t
, then so on down the chain. The promotion will ensure that the answer is both unsigned and that the requested bits remain present. The final cast then reduces it back to the desired type.
This is really simple and elegant, and I wish I had thought of it a year ago. Thank you to everyone who responded before.