C ++에서 바닥, 천장 및 바깥 쪽 반올림 모드로 정수 나누기
최근에 나는 ceil rounding (양의 무한대로)으로 정수를 나누는 방법을 묻는 이 질문 을 보았습니다 . 불행히도 대답은 부호있는 정수에 대해 작동하지 않거나 언더 플로 및 오버플로에 문제가 있습니다.
예를 들어 허용되는 답변 에는 다음과 같은 솔루션이 있습니다.
q = 1 + ((x - 1) / y);
때 x제로, 거기에 16,777,215 ~0와 결과가 올바르지 않습니다.
부호있는 정수와 부호없는 정수에 대해 천장 반올림을 올바르게 구현 하는 방법과 바닥 (음의 무한대 방향) 및 바깥 쪽 (0에서 멀어짐 )과 같은 다른 반올림 모드를 어떻게 구현 합니까?
답변
C ++에서 /나누기 연산 은 기본적으로 자르기 (0으로)를 사용하여 반올림 합니다. 다른 반올림 모드를 구현하기 위해 나눗셈 결과를 0으로 조정할 수 있습니다. 나눗셈에 나머지가 없으면 반올림이 필요하지 않기 때문에 모든 반올림 모드가 동일합니다.
이를 염두에두고 다양한 반올림 모드를 구현할 수 있습니다. 그러나 시작하기 전에 반환 유형에 대한 도우미 템플릿이 필요하므로 auto모든 곳에서 반환 유형을 사용하지 않습니다 .
#include <type_traits>
/**
* Similar to std::common_type_t<A, B>, but if A or B are signed, the result will also be signed.
*
* This differs from the regular type promotion rules, where signed types are promoted to unsigned types.
*/
template <typename A, typename B>
using common_signed_t =
std::conditional_t<std::is_unsigned_v<A> && std::is_unsigned_v<B>,
std::common_type_t<A, B>,
std::common_type_t<std::make_signed_t<A>, std::make_signed_t<B>>>;
Ceil (+ ∞ 방향)
Ceil 반올림은 음의 몫에 대한 반올림 자르기와 동일 하지만 양의 몫과 0이 아닌 나머지의 경우 0에서 반올림합니다. 이것은 0이 아닌 나머지에 대한 몫을 증가 시킨다는 것을 의미합니다.
덕분에 if-constexpr우리는 하나의 함수만으로 모든 것을 구현할 수 있습니다.
template <typename Dividend, typename Divisor>
constexpr common_signed_t<Dividend, Divisor> div_ceil(Dividend x, Divisor y)
{
if constexpr (std::is_unsigned_v<Dividend> && std::is_unsigned_v<Divisor>) {
// quotient is always positive
return x / y + (x % y != 0); // uint / uint
}
else if constexpr (std::is_signed_v<Dividend> && std::is_unsigned_v<Divisor>) {
auto sy = static_cast<std::make_signed_t<Divisor>>(y);
bool quotientPositive = x >= 0;
return x / sy + (x % sy != 0 && quotientPositive); // int / uint
}
else if constexpr (std::is_unsigned_v<Dividend> && std::is_signed_v<Divisor>) {
auto sx = static_cast<std::make_signed_t<Dividend>>(x);
bool quotientPositive = y >= 0;
return sx / y + (sx % y != 0 && quotientPositive); // uint / int
}
else {
bool quotientPositive = (y >= 0) == (x >= 0);
return x / y + (x % y != 0 && quotientPositive); // int / int
}
}
언뜻보기에 부호있는 유형의 구현은 정수 나누기와 모듈로 나누기를 모두 사용하기 때문에 비용이 많이 드는 것 같습니다. 그러나 현대 아키텍처에서 부서는 일반적으로 나머지가 있는지 여부를 나타내는 플래그를 설정하므로이 x % y != 0경우 완전히 무료입니다.
몫을 먼저 계산하지 않고 몫이 양수인지 확인하는 이유가 궁금 할 수도 있습니다. 이 분할 중에 이미 정밀도를 잃었 기 때문에 작동하지 않았으므로 나중에이 테스트를 수행 할 수 없습니다. 예를 들면 :
-1 / 2 = -0.5
// C++ already rounds towards zero
-0.5 -> 0
// Now we think that the quotient is positive, even though it is negative.
// So we mistakenly round up again:
0 -> 1
플로어 (-∞ 쪽)
바닥 반올림은 양의 몫의 경우 자르기 와 동일 하지만 음의 몫의 경우 0에서 반올림합니다. 이것은 0이 아닌 나머지에 대한 몫을 감소 시킨다는 것을 의미합니다.
template <typename Dividend, typename Divisor>
constexpr common_signed_t<Dividend, Divisor> div_floor(Dividend x, Divisor y)
{
if constexpr (std::is_unsigned_v<Dividend> && std::is_unsigned_v<Divisor>) {
// quotient is never negative
return x / y; // uint / uint
}
else if constexpr (std::is_signed_v<Dividend> && std::is_unsigned_v<Divisor>) {
auto sy = static_cast<std::make_signed_t<Divisor>>(y);
bool quotientNegative = x < 0;
return x / sy - (x % sy != 0 && quotientNegative); // int / uint
}
else if constexpr (std::is_unsigned_v<Dividend> && std::is_signed_v<Divisor>) {
auto sx = static_cast<std::make_signed_t<Dividend>>(x);
bool quotientNegative = y < 0;
return sx / y - (sx % y != 0 && quotientNegative); // uint / int
}
else {
bool quotientNegative = (y < 0) != (x < 0);
return x / y - (x % y != 0 && quotientNegative); // int / int
}
}
구현은의 구현과 거의 동일합니다 div_ceil.
제로에서 멀리
0에서 멀리 떨어져있는 것은 truncate의 정반대입니다 . 기본적으로 몫의 부호에 따라 증감해야하지만 나머지가있는 경우에만 필요합니다. sgn결과에 몫을 더하는 것으로 표현할 수 있습니다 .
template <typename Int>
constexpr signed char sgn(Int n)
{
return (n > Int{0}) - (n < Int{0});
};
이 도우미 함수를 사용하여, 우리는 완벽하게 구현할 수 까지 반올림 :
template <typename Dividend, typename Divisor>
constexpr common_signed_t<Dividend, Divisor> div_up(Dividend x, Divisor y)
{
if constexpr (std::is_unsigned_v<Dividend> && std::is_unsigned_v<Divisor>) {
// sgn is always 1
return x / y + (x % y != 0); // uint / uint
}
else if constexpr (std::is_signed_v<Dividend> && std::is_unsigned_v<Divisor>) {
auto sy = static_cast<std::make_signed_t<Divisor>>(y);
signed char quotientSgn = sgn(x);
return x / sy + (x % sy != 0) * quotientSgn; // int / uint
}
else if constexpr (std::is_unsigned_v<Dividend> && std::is_signed_v<Divisor>) {
auto sx = static_cast<std::make_signed_t<Dividend>>(x);
signed char quotientSgn = sgn(y);
return sx / y + (sx % y != 0) * quotientSgn; // uint / int
}
else {
signed char quotientSgn = sgn(x) * sgn(y);
return x / y + (x % y != 0) * quotientSgn; // int / int
}
}
해결되지 않은 문제
안타깝게도 이러한 함수는 가능한 모든 입력에 대해 작동하지 않으므로 해결할 수없는 문제입니다. 예를 들어 32 비트 부호있는 정수를 사용하여 표현할 수없는 uint32_t{3 billion} / int32_t{1}결과를 나눕니다 int32_t(3 billion). 이 경우 언더 플로가 발생합니다.
더 큰 반환 유형을 사용하는 것은 더 큰 대안이없는 64 비트 정수를 제외한 모든 옵션에 사용할 수 있습니다. 따라서 서명되지 않은 숫자를이 함수에 전달할 때 서명 된 표현과 동일한 지 확인하는 것은 사용자의 책임입니다.