Overflow bei Integeraddition

Hallo, gibt es irgend eine Möglichkeit festzustellen, ob bei der Addition zweier unsigned integers ein Overflow aufgetreten ist?
Der Einzige Ansatz, der Mir einfallen würe, wäre:

bool overflow(unsigned int a, unsigned int b)
{
    unsigned int tmp = a;
    tmp+=b;

    if(a>tmp || b>tmp)
        return true;
    return false;
}

Geht das nicht irgendwie eleganter?

#include <iostream>
#include <climits>
using namespace std;

bool uintAddOverflowTest(unsigned int left, unsigned int right)
{
    return (UINT_MAX - left) < right;
}

int main()
{
    cout << uintAddOverflowTest(4294967290, 123) << endl;
}

Gibt es irgendeinen Grund, nicht folgendes zu machen:

bool add_a(uint& a, const uint& b)
{
   a+=b;
   return a<b;
}

Sollte das nicht deutlich performanter und portabler sein, als die hier vorgeschlagene Methode?

bool add_b(uint& a, const uint& b)
{
   bool uebertrag = (UINT_MAX - a) < b;
   a+=b;
   return uebertrag;
}

Oder gibt es Fälle, in denen add_a falsch ist?

Werner Salomon

Olrig schrieb:

Gibt es irgendeinen Grund, nicht folgendes zu machen:
bool add_a(uint& a, const uint& b)
{
   a+=b;
   return a<b;
}
Sollte das nicht deutlich performanter und portabler sein, als die hier vorgeschlagene Methode?

performanter vielleicht, portabler sicher nicht. Meines Wissens ist gar nicht definiert, was bei a herauskommt, wenn ein overflow auftritt. Portabel wäre es sicher dann, wenn man std::numeric_limits< uint >::max() als Maximalwert verwendet.

Im Übrigen würde ich eine eigene Klasse für diese unsigned int mit Überlaufkontrolle und Exception vorschlagen. Das sähe ungefähr so aus:

#include <iostream>
#include <stdexcept>
#include <limits>

namespace detail
{
    void checkOverflowOnPlus( unsigned int a, unsigned int b )
    {
        if( a > std::numeric_limits< unsigned int >::max() - b )
            throw std::overflow_error( "Addition zweier unsigned int überschreitet das Limit" );
    }
}

class UInt
{
public:
    UInt( unsigned int x = 0 ) : m_x( x ) {}
    UInt& operator+=( const UInt& b )
    {
        return add( b.m_x );
    }
    UInt& operator+=( unsigned int b )
    {
        return add( b );
    }
    friend std::ostream& operator<<( std::ostream& out, const UInt& i )
    {
        return out << i.m_x;
    }
private:
    UInt& add( unsigned int b )
    {
        detail::checkOverflowOnPlus( m_x, b );
        m_x += b;
        return *this;
    }
    unsigned int m_x;
};

UInt operator+( UInt a, const UInt& b )
{
    return a += b;
}
UInt operator+( UInt a, unsigned int b )
{
    return a += b;
}
UInt operator+( unsigned int a, UInt b )
{
    return b += a;
}

int main()
{
    using namespace std;
    UInt a1 = 2314;
    cout << (123456u + a1) << endl;
    return 0;
}

Der Vorteil ist, dass man damit genauso Code schreiben kann, wie mit normalen unsigned int. Über ein typedef kann dann schnell mal umschalten.
.. könnte man auch noch sehr schön 'templatisieren' - boost lässt grüßen.

Gruß
Werner

Werner Salomon schrieb:

Meines Wissens ist gar nicht definiert, was bei a herauskommt, wenn ein overflow auftritt

Ist das nich durch den Standard gesichert? Nämlich immer die Zahl modulo Max_int (zumindest bei unsigned integers).

SeppJ

Olrig schrieb:

Werner Salomon schrieb:

Meines Wissens ist gar nicht definiert, was bei a herauskommt, wenn ein overflow auftritt

Ist das nich durch den Standard gesichert? Nämlich immer die Zahl modulo Max_int (zumindest bei unsigned integers).

Für unsigned Typen ist es gesichert, für andere ist das Ergebnis undefiniert (allerdings ist das Zweierkomplement die vorherrschende Art der Darstellung negativer Zahlen, so dass bei Überlauf von signed Typen auf fast jedem System das herauskommt, was man beim Zweierkomplement erwartet).

Mal eine etwas andere frage: Ich habe diesen Algorithmus zum bitweisen addieren von unsigned intergers gefunden:

unsigned int add(unsigned int a, unsigned int b)
{
    unsigned int sum   = a ^ b;
    unsigned int carry = a & b;

    while(carry)
    {
        carry<<=1;
        a = sum;
        sum = a ^ carry;
        carry = a & carry;
    }
    return sum;
}

Der Algorithmus funktioniert auch einwandfrei. Aber kann ich irgendwie auf der "Bitebene" oder im Verlauf des Algorithmus ablesen, ob bei ein Overflow aufgetreten ist?

freaky

Werner Salomon schrieb:

...

Werner Salomon zeigt wie immer eine gute Lösung .
@Olrig, eig. solltest du das von Werner Salomon übernehmen können und einfach die anderen Operatoren überladen.

camper

Olrig schrieb:

Aber kann ich irgendwie auf der "Bitebene" oder im Verlauf des Algorithmus ablesen, ob bei ein Overflow aufgetreten ist?

Dann, wenn carry<<=1 das Ergebnis 0 liefert.

[quote="Olrig"]Gibt es irgendeinen Grund, nicht folgendes zu machen:

bool add_a(uint& a, const uint& b)
{
   a+=b;
   return a<b;
}

Sollte das nicht deutlich performanter und portabler sein, als die hier vorgeschlagene Methode?

Olrig schrieb:

...
Oder gibt es Fälle, in denen add_a falsch ist?

Solche Fälle gibt es nicht!

a < b ? (0x100000000+a) : a

Superlexx

Für den unsigned - Fall nehme ich normalerweise
const bool isOverflowed = a + b < a;

Für den Allgemeinfall dann doch lieber den SafeInt.

camper schrieb:

Olrig schrieb:

Aber kann ich irgendwie auf der "Bitebene" oder im Verlauf des Algorithmus ablesen, ob bei ein Overflow aufgetreten ist?

Dann, wenn carry<<=1 das Ergebnis 0 liefert.

Aber die Funktion wir ja erst verlassen, WENN carry == 0 ist. Das heißt ich müsste VOR dem letzten Schleifendurchlauf testen, ob das höchstwertigste Bit in carry gesetzt ist?