Tam sayıları C ++ 'da yer, tavan ve dışa yuvarlama modlarıyla bölün
Son zamanlarda, tam sayıları tavan yuvarlamasıyla (pozitif sonsuza doğru) nasıl bölebileceğinizi soran bu soruyu gördüm . Maalesef cevaplar ya işaretli tamsayılar için işe yaramıyor ya da yetersizlik ve taşma sorunları var.
Örneğin, kabul edilen yanıt şu çözüme sahiptir:
q = 1 + ((x - 1) / y);
Zaman xsıfırdır, orada bir Yetersizlik ~0ve sonuç yanlış.
Nasıl uygulayabilir ceil imzalı ve imzasız tamsayı ve nasıl uygularım diğer yuvarlama gibi modlar için doğru yuvarlama kat (negatif sonsuza doğru) ve dışa doğru (sıfırdan uzağa)?
Yanıtlar
C ++ 'da, /bölme işlemi varsayılan olarak kes (sıfıra doğru) kullanarak yuvarlanır . Diğer yuvarlama modlarını uygulamak için bölmenin sonucunu sıfıra doğru ayarlayabiliriz. Bölmenin kalanı olmadığında, yuvarlama gerekmediği için tüm yuvarlama modlarının eşdeğer olduğunu unutmayın.
Bunu akılda tutarak, farklı yuvarlama modlarını uygulayabiliriz. Ancak başlamadan önce, dönüş türleri için bir yardımcı şablona ihtiyacımız olacak, böylece autoher yerde dönüş türlerini kullanmayacağız :
#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>>>;
Tavan (+ ∞'a doğru)
Ceil yuvarlama ile aynıdır kesecek negatif katsayılar için yuvarlama, fakat pozitif katsayılar ve sıfır olmayan kalanlarını biz yuvarlak uzak sıfırdan. Bu, sıfır olmayan kalanlar için bölümü artırdığımız anlamına gelir.
Sayesinde if-constexpr, her şeyi yalnızca tek bir işlevi kullanarak gerçekleştirebiliriz:
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
}
}
İlk bakışta, işaretli tipler için uygulamalar pahalı görünüyor, çünkü hem bir tamsayı bölümü hem de bir modulo bölümü kullanıyorlar. Bununla birlikte, modern mimarilerde bölüm tipik olarak bir kalan olup olmadığını gösteren bir bayrak belirler x % y != 0, bu durumda bu durumda tamamen ücretsizdir.
Ayrıca neden önce bölümü hesaplamadığımızı ve ardından bölümün pozitif olup olmadığını kontrol etmediğimizi merak ediyor olabilirsiniz. Bu işe yaramaz çünkü bu bölünme sırasında hassasiyeti zaten kaybettik, bu yüzden bu testi daha sonra yapamayız. Örneğin:
-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
Zemin (-∞'a doğru)
Zemin yuvarlama ile aynıdır truncate pozitif katsayılar için değil, negatif katsayılar için biz yuvarlak sıfırdan uzağa. Bu, sıfır olmayan kalanlar için bölümü azalttığımız anlamına gelir.
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
}
}
Uygulama ile neredeyse aynıdır div_ceil.
Sıfırdan Uzakta
Dışarıda sıfırdan tam tersidir Kesik . Temel olarak, bölümün işaretine bağlı olarak artırmamız veya azaltmamız gerekir, ancak yalnızca kalan varsa. Bu sgn, bölümün sonuca eklenmesi olarak ifade edilebilir :
template <typename Int>
constexpr signed char sgn(Int n)
{
return (n > Int{0}) - (n < Int{0});
};
Bu yardımcı işlevi kullanarak yukarı yuvarlamayı tam olarak uygulayabiliriz :
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
}
}
Çözülmemiş Sorunlar
Maalesef bu işlevler tüm olası girdiler için çalışmayacaktır ki bu çözemeyeceğimiz bir sorundur. Örneğin, 32 bitlik işaretli bir tamsayı kullanılarak gösterilemeyen uint32_t{3 billion} / int32_t{1}sonuçları bölmek int32_t(3 billion). Bu durumda yetersiz kalırız.
Daha büyük dönüş türlerini kullanmak, daha büyük bir alternatifin olmadığı 64 bitlik tam sayılar dışında her şey için bir seçenek olacaktır. Bu nedenle, bu işleve işaretsiz bir numara geçtiklerinde, imzalı temsiline eşdeğer olmasını sağlamak kullanıcının sorumluluğundadır.