Schneller als Karatsuba

Gary

Original erstellt von volkard:
das shiften kostet doch lineare zeit, also dat ganze ding n^2. oder?

Könntest Recht haben.
Aber...
Das Shiften ist auf jeden Fall schneller als eine Multiplikation. :p
So könnte ich Karatsuba noch übertrumpfen.

Gary

@Doktor Prokt:
Was meinst du mit Stellen?
Meinst du, dass HUGE_MAX nur eine 2er-Potenz sein darf?
Ist es nicht möglich, dass ich das Array so definiere:

unsigned short harr[45];

Teil mal eine 45stellige Zahl in zwei Zahlen mit gleich vielen Stellen auf.
Das geht irgendwie nicht, d.h. du musst hier schon die Schulmethode anwenden oder besser halt die 45stellige Zahl in ein 64er array (nächste Zweierpotenz) einbetten.

Gary

Wieso 45-stellig
Die Zahl hat ja 216 Stellen. Das Array umfasst halt 45 Elemente = 45*16 Bits.
und... Ich will es ja auch gar nicht aufspalten.

Sorry, habe deine Doku nicht richtig überlesen. Im Karatsuba-Algorithmus hat "Aufspalten" eine andere Bedeutung als bei dir.

Gary

Wie hast du das mit dem Dividieren gemacht? Ich würde es so lösen, dass ich das Ergebnis vorher eingrenze, und dann alle Zahlen von unterster bis oberster Grenze ausprobiere, bis Zahl * Nenner > Zähler, das Ergebnis wäre dann Zahl-1.
Ist aber ziemlich langsam, wenn große Zahlen durch extrem kleine dividiert werden. Gibts da was besseres?

Mr. N

@Gary: also ich seh da kein komplexes (edit: im sinne von kompliziert) dividieren

[ Dieser Beitrag wurde am 09.12.2002 um 13:23 Uhr von Mr. N editiert. ]

Gary

Division ist schon abgehakt (Habs mit bitweiser Approximation gelöst).
Kann mir jemand bei der Ausgabe / Eingabe helfen? Bitte...
Ich muss eine Zahl vom Binärsystem ins Dezimalsystem umwandeln.
Siehe diesen Thread
Vielen Dank im Voraus.

[ Dieser Beitrag wurde am 09.12.2002 um 19:17 Uhr von Gary editiert. ]

Gary

Original erstellt von Doktor Prokt:Gib mal den ganzen Code, dann vergleich ich den mit meiner Karatsuba-Implementierung. Macht jedenfalls mehr Spaß als ein rein theoretischer Vergleich.

Jetzt kommt mein langer Thread
Nachdem mit keiner helfen wollte, hab ich es irgendwie gelöst (Ausgabe ist nicht sehr effizient.

#ifndef HUGENAT_HPP
#define HUGENAT_HPP

// Name:
//      hugenat.hpp

// Inhalt:
//      Integer-Berechnungen mit natürlichen Zahlen bis (theoretisch) unendlich machen können.
//      (Die Rechnerarchitektur gibt hier die Grenzen vor). Es gelten die Rechenregeln für
//      natürliche Zahlen.

// Autor:
//      Gernot Fritz (2002)

// Klassenname:
//      HugeNatural

// Benötigte Includes:
#include "./bitalg.hpp" // Bit-Arithmetik
#include <iostream>

// Globale Konstante, die die Array-Grösse des short-Arrays festlegt.
// Kann natürlich beliebig verändert werden.

// höchstmögliche Zahl ist 2^(16 * HUGE_MAX) -1
const size_t HUGE_MAX = 64;
// max. Dezimalstellen ~ HUGE_MAX * 4,82

// Die Zahl wird auf 16Bit Basis in einem short-Array gespeichert.
// Ein Element beinhaltet 16 Bits.
// (= minimaler Speicherverbrauch und sehr schnell)
class HugeNatural
{
    // Arithmetische Operatoren
    friend HugeNatural& operator+=(HugeNatural& lhs,const HugeNatural& rhs);
    friend HugeNatural& operator-=(HugeNatural& lhs,const HugeNatural& rhs);
    friend HugeNatural& operator*=(HugeNatural& lhs,const HugeNatural& rhs);
    friend HugeNatural& operator/=(HugeNatural& lhs,const HugeNatural& rhs);
    friend HugeNatural& operator%=(HugeNatural& lhs,const HugeNatural& rhs);

    // Inkrement / Dekrement (postfix und präfix)
    friend HugeNatural& operator++(HugeNatural& hn);
    friend HugeNatural& operator--(HugeNatural& hn);
    friend HugeNatural operator++(HugeNatural& hn,int);
    friend HugeNatural operator--(HugeNatural& hn,int);

    // Ausgabe / Eingabe
    friend std::ostream& operator<<(std::ostream& os,const HugeNatural& hn);
    friend std::istream& operator>>(std::istream& is, HugeNatural& hn);

private:
    unsigned short m_harr[HUGE_MAX];
    size_t m_bc; // speichert, wieviele Elemente benutzt werden

    void SetZero(); // Array NULL setzen

public:
    HugeNatural(); // HugeNatural = 0
    HugeNatural(unsigned long var);
    HugeNatural(const HugeNatural& hn);
    ~HugeNatural() {}

    HugeNatural& operator=(const HugeNatural& hn);

    size_t GetBC() const { return m_bc;}

    // Vergleich
    bool IsEqual(const HugeNatural& hn) const;
    bool IsLessThan(const HugeNatural& hn) const;

    bool IsEven() const // Ist die Zahl gerade? (d.h. ohne Rest durch 2 teilbar)
    {
        if(bit::IsSet(m_harr[0],0))
            return false;
        return true;
    }
    bool IsOdd() const // Ist die Zahl ungerade?
    {
        if(bit::IsSet(m_harr[0],0))
            return true;
        return false;
    }
    bool IsZero() const // Ist sie NULL ?
    {
        for(size_t i=0;i<HUGE_MAX;++i)
        {
            if(m_harr[i]!=0)
                return false;
        }
        return true;
    }

    // Prüfen, ob Bit bn in index gesetzt ist
    bool BitSet(size_t index, unsigned char bn) const
    {
        if(bit::IsSet(m_harr[index],bn))
            return true;
        return false;
    }
    unsigned short GetElement(size_t index) const
    {
        return m_harr[index];
    }

    // Folgende 2 Funktionen sind sehr schnell
    void DivideBy2(); // (Integer) Division durch 2 = Bit Shift um eine Stelle nach rechts
    void MultiplyBy2(); // Multiplikation mit 2 = Bit Shift um eine Stelle nach links

    // Short / Long Konvertierung
    bool IsLong() const { return (m_bc<=2);}
    bool IsShort() const { return (m_bc<=1);}
    unsigned long Long() const
    {
        if(m_bc==1) // Muss sein, da das Element m_harr[1] nicht NULL sein muss
            return m_harr[0];
        return m_harr[0] + (m_harr[1]<<16); // nur die ersten zwei Elemente werden zurückgegeben
    }
    unsigned short Short() const { return m_harr[0];} // nur das erste Element wird zurückgegeben
};

// Vergleichsoperatoren
bool operator==(const HugeNatural& lhs, const HugeNatural& rhs)
    { return lhs.IsEqual(rhs);}
bool operator!=(const HugeNatural& lhs, const HugeNatural& rhs)
    { return !lhs.IsEqual(rhs);}
bool operator<(const HugeNatural& lhs, const HugeNatural& rhs)
    { return lhs.IsLessThan(rhs);}
bool operator>(const HugeNatural& lhs, const HugeNatural& rhs)
    { return rhs.IsLessThan(lhs);}
bool operator<=(const HugeNatural& lhs, const HugeNatural& rhs)
    { return lhs.IsLessThan(rhs) || lhs.IsEqual(rhs); }
bool operator>=(const HugeNatural& lhs, const HugeNatural& rhs)
    { return rhs.IsLessThan(lhs) || lhs.IsEqual(rhs);}

// Arithmetische Operatoren
HugeNatural operator+(const HugeNatural& fo,const HugeNatural& so)
{
    HugeNatural tmp = fo;
    tmp+=so;
    return tmp;
}

HugeNatural operator-(const HugeNatural& fo,const HugeNatural& so)
{
    HugeNatural tmp = fo;
    tmp-=so;
    return tmp;
}

HugeNatural operator*(const HugeNatural& fo,const HugeNatural& so)
{
    HugeNatural tmp = fo;
    tmp*=so;
    return tmp;
}

HugeNatural operator/(const HugeNatural& fo,const HugeNatural& so)
{
    HugeNatural tmp = fo;
    tmp/=so;
    return tmp;
}

HugeNatural operator%(const HugeNatural& fo,const HugeNatural& so)
{
    HugeNatural tmp = fo;
    tmp%=so;
    return tmp;
}

////////////////////////////////////////////////////////////////////////////////////

// Konstruktoren
HugeNatural::HugeNatural()
{
    SetZero();
    m_bc=1;
}

HugeNatural::HugeNatural(unsigned long var)
{
    SetZero();
    m_harr[0] = bit::Part1(var);
    m_harr[1] = bit::Part2(var);
    if(m_harr[1]==0) // var passt in einen short Bereich
        m_bc=1;
    else
        m_bc=2;
}

HugeNatural::HugeNatural(const HugeNatural& hn)
{
    SetZero();
    m_bc = hn.m_bc;
    for(size_t i=0;i<HUGE_MAX;++i)
        m_harr[i] = hn.m_harr[i];
}

HugeNatural& HugeNatural::operator=(const HugeNatural& hn)
{
    if(this==&hn)
        return *this;
    SetZero();
    m_bc = hn.m_bc;
    for(size_t i=0;i<HUGE_MAX;++i)
        m_harr[i] = hn.m_harr[i];
    return *this;
}

// Array NULL setzen
void HugeNatural::SetZero()
{
    for(size_t i=0;i<HUGE_MAX;++i)
        m_harr[i] = 0;
}

// Inkrement / Dekrement (postfix und präfix)
HugeNatural& operator++(HugeNatural& hn)
{
    size_t i=0;
    unsigned char bn=0;

    for(;;)
    {
        if(bn==16) // Ein Element weiter gehen
        {
            bn=0;
            ++i;
        }
        if(bit::IsSet(hn.m_harr[i],bn))
            bit::Clear(hn.m_harr[i],bn);
        else
        {
            bit::Set(hn.m_harr[i],bn);
            if(i==hn.m_bc) // Falls Übertrag in Element m_bc
                ++hn.m_bc;
            return hn;          
        }
        ++bn;
    }
}

HugeNatural operator++(HugeNatural& hn,int)
{
    HugeNatural tmp = hn;
    ++hn;
    return tmp;
}

HugeNatural& operator--(HugeNatural& hn)
{
    if(hn.IsZero())
        return hn;
    size_t i=0;
    unsigned char bn=0;

    for(;;)
    {
        if(bn==16) // Ein Element weiter gehen
        {
            bn=0;
            ++i;
        }
        if(!bit::IsSet(hn.m_harr[i],bn))
            bit::Set(hn.m_harr[i],bn);
        else
        {
            bit::Clear(hn.m_harr[i],bn);
            if((i==(hn.m_bc-1)) && (hn.m_harr[i]==0)) // Wenn das niedrigste Bit in m_harr[m_bc-1]
                --hn.m_bc;                        // gelöscht wurde, m_bc verringern
            return hn;
        }
        ++bn;
    }
}

HugeNatural operator--(HugeNatural& hn,int)
{
    HugeNatural tmp = hn;
    --hn;
    return tmp;
}

// Vergleich
bool HugeNatural::IsEqual(const HugeNatural& hn) const
{
    for(size_t i=0;i<HUGE_MAX;++i)
    {
        if(m_harr[i]!=hn.m_harr[i])
            return false;
    }
    return true;
}

bool HugeNatural::IsLessThan(const HugeNatural& hn) const
{
    if(m_bc < hn.m_bc)
        return true;
    if(m_bc > hn.m_bc)
        return false;
    for(size_t i=m_bc-1;;--i)
    {
        if(m_harr[i] < hn.m_harr[i])
            return true;
        if(m_harr[i] > hn.m_harr[i])
            return false;
        if(i==0 && (m_harr[i] == hn.m_harr[i]))
            return false;
        if(i==0)
            return true;
    }
}

// Multiplizieren und Dividieren durch 2
void HugeNatural::DivideBy2()
{
    if(IsZero()) // 0/2 = 0
        return;
    bool carry=false, carry_tmp=false;

    if(m_harr[m_bc-1]==1) // Übertrag behandeln
    {
        carry=true;
        --m_bc;
        bit::Clear(m_harr[m_bc],0); // niedrigstes Bit löschen
    }
    for(size_t i=m_bc;i!=0;--i)
    {
        if(bit::IsSet(m_harr[i-1],0))
            carry_tmp=true; // niedrigstes Bit merken
        else
            carry_tmp=false;
        m_harr[i-1]>>=1; // Bit Shift nach rechts um eine Stelle = Division durch 2
        if(carry)
            bit::Set(m_harr[i-1],15); // höchstes Bit setzen
        carry=carry_tmp;
    }
}

void HugeNatural::MultiplyBy2()
{
    if(IsZero()) // 0*2 = 0
        return;
    bool carry=false, carry_tmp=false;
    for(size_t i=0;i<m_bc;++i)
    {
        if(bit::IsSet(m_harr[i],15))
            carry_tmp=true; // höchstes Bit merken
        else
            carry_tmp=false;
        m_harr[i]<<=1; // Bit Shift nach links um eine Stelle = Multiplikation mit 2
        if(carry)
            bit::Set(m_harr[i],0); // niedrigstes Bit setzen
        carry=carry_tmp;
    }
    if(carry) // Übertrag behandeln
    {
        bit::Set(m_harr[m_bc],0);
        ++m_bc;
    }
}

// Arithmetische Operatoren
HugeNatural& operator+=(HugeNatural& lhs,const HugeNatural& rhs)
{
    bool carry = false;
    unsigned char bn = 0; // Bitnummer
    if(lhs.m_bc<rhs.m_bc)
        lhs.m_bc = rhs.m_bc;

    for(size_t i=0;i<lhs.m_bc;++i)
    {
        for(bn=0;bn<16;++bn)
        {
            if(carry) // Übertrag behandeln
            {
                if(bit::IsSet(lhs.m_harr[i],bn))
                    bit::Clear(lhs.m_harr[i],bn);
                else
                {
                    bit::Set(lhs.m_harr[i],bn);
                    carry=false;
                }
            }
            if(bit::IsSet(lhs.m_harr[i],bn) && bit::IsSet(rhs.m_harr[i],bn)) // 1+1=0 | Übertrag 1
            {
                bit::Clear(lhs.m_harr[i],bn); // Bit löschen
                carry=true; // Übertrag = 1
            }
            else if(!bit::IsSet(lhs.m_harr[i],bn) && bit::IsSet(rhs.m_harr[i],bn)) // 0+1
                bit::Set(lhs.m_harr[i],bn); // Bit setzen
            // Die anderen Möglichkeiten müssen nicht überprüft werden, da sich dabei
            // nichts ändert. 0+0 = 0, 1+0 = 1
        }
    }
    if(carry) // letzten Übertrag behandeln
    {
        bit::Set(lhs.m_harr[lhs.m_bc],0);
        ++lhs.m_bc;
    }
    return lhs;
}

HugeNatural& operator-=(HugeNatural& lhs,const HugeNatural& rhs)
{
    bool carry = false;
    if(lhs.IsLessThan(rhs))
    {
        lhs.SetZero();
        lhs.m_bc = 1;
        return lhs;
    }
    for(size_t i=0;i<lhs.m_bc;++i)
    {
        for(unsigned char bn=0;bn<16;++bn)
        {
            if(carry) // Übertrag behandeln
            {
                if(bit::IsSet(lhs.m_harr[i],bn))
                {
                    bit::Clear(lhs.m_harr[i],bn);
                    carry=false;
                }
                else
                    bit::Set(lhs.m_harr[i],bn);
            }
            if(bit::IsSet(lhs.m_harr[i],bn) && bit::IsSet(rhs.m_harr[i],bn)) // 1-1=0
                bit::Clear(lhs.m_harr[i],bn);

            else if(!bit::IsSet(lhs.m_harr[i],bn) && bit::IsSet(rhs.m_harr[i],bn)) // 0-1=1 | Übertrag 1
            {
                bit::Set(lhs.m_harr[i],bn); // Bit setzen
                carry=true; // Übertrag = 1
            }
            // Die anderen Möglichkeiten müssen nicht überprüft werden, da sich dabei
            // nichts ändert. 0-0 = 0, 1-0 = 1
        }
    }
    return lhs;
}

// Beim Multiplizieren wird ausgenutzt, dass man die Faktoren aufspalten kann.
// Z.B.: 13 * 17 = 13 * (16 + 1) =  13 * 16 + 13 * 1
// Zuerst wird überprüft, ob der 2. Faktor gerade ist. Wenn er gerade ist, wird er durch 2
// dividiert und der 1. Faktor mit 2 multipliziert. Dabei gibt es dann keine Veränderung
// des Produkts.
// Z.B.: 13 * 16 = (13 * 2) * (16 / 2) = 26 * 8
// Wenn der 2. Faktor ungerade ist, wird er aufgespalten (d.h. Dekrement) und die
// Zwischenergebnisse werden in tmp_count gespeichert.
// Das wird solange gemacht, bis der 2. Faktor = 1 ist.

// Noch ein paar Sätze zur Geschwindigkeit des Algorithmus:
// 1)   Die beiden Funktionen DivideBy2 und MultiplyBy2 sind reine Bit-Shift Funktionen
//      -> schneller als Multiplikationen
// 2)   Auch op-- und op+= basieren auf Bit-Funktionen -> Geschwindigkeitsvorteil
// 3)   Im ungünstigsten Fall (alle Bits sind gesetzt), benötigt der Algorithmus maximal
//      n / 4,82 * 16 * 2 (= n * 6,64) Schleifendurchläufe, wobei n = max. Dezimalstellen.
// 4)   Im günstigsten Fall (nur ein Bit ist gesetzt), benötigt man maximal
//      n / 4,82 * 16 (= n * 3,32) Schleifendurchläufe (also die Hälfte).
// 5)   Das ist deutlich schneller als die Schulmethode (n^2) und die
//      Multiplikations-Algorithmen von Karatsuba (n^1,59) und Dr. Seltsam (n^1,2)

HugeNatural& operator*=(HugeNatural& lhs,const HugeNatural& rhs)
{
    if(lhs.IsZero())
        return lhs;
    if(rhs.IsZero())
    {
        lhs.SetZero();
        return lhs;
    }

    HugeNatural tmp = rhs;
    HugeNatural tmp_count;

    while(tmp!=1)
    {
        if(tmp.IsEven())
        {
            tmp.DivideBy2(); // Bit Shift nach rechts
            lhs.MultiplyBy2(); // Bit Shift nach links
        }
        else
        {
            --tmp; // Dekrement braucht nur einen Durchlauf, weil die Zahl ungerade ist
            tmp_count+=lhs;
        }
    }
    lhs+=tmp_count;
    return lhs;
}

// Extrem schnell
HugeNatural& operator/=(HugeNatural& lhs,const HugeNatural& rhs)
{
    if(rhs.IsZero() || lhs.IsZero() || rhs.IsEqual(1))
        return lhs;
    if(lhs.IsLessThan(rhs)) // -> lhs = 0
    {
        lhs.SetZero();
        lhs.m_bc = 1;
        return lhs;
    }
    if(rhs.IsEqual(lhs)) // -> lhs = 1
    {
        lhs.SetZero();
        lhs.m_bc = 1;
        bit::Set(lhs.m_harr[0],0);
        return lhs;
    }

    HugeNatural tmp = rhs;

    while(lhs.IsEven() && tmp.IsEven())
    {
        lhs.DivideBy2(); // "Kürzen" von Zähler
        tmp.DivideBy2(); // und Nenner durch 2
    }
    if(tmp.IsEqual(1)) // Man konnte durch rhs kürzen
        return lhs;

    // erg = lhs / tmp -> lhs = erg * tmp
    HugeNatural erg;
    erg.m_bc=lhs.m_bc;

    // Durch schrittweise Approximation nähern wir uns dem Ergebnis.
    // Benötigte Durchläufe: lhs.m_bc * 16
    for(size_t i=erg.m_bc-1;;--i)
    {
        for(unsigned char bn=15;;--bn)
        {
            bit::Set(erg.m_harr[i],bn); // Bit setzen
            if(lhs<(tmp*erg)) // Wenn lhs/tmp < erg ist,
                bit::Clear(erg.m_harr[i],bn); // dann Bit wieder löschen
            if(bn==0)
                break;
        }
        if(i==0)
            break;
    }
    // m_bc bestimmen
    for(i=erg.m_bc-1;;--i)
    {
        for(unsigned char bn=15;;--bn)
        {
            if(bit::IsSet(erg.m_harr[i],bn)) // Wenn das Bit gesetzt ist, dann m_bc = i+1
            {
                erg.m_bc = ++i; // Inkrement ist schneller als Addition
                lhs = erg;
                return lhs;
            }
            if(bn==0)
                break;
        }
    }
}

HugeNatural& operator%=(HugeNatural& lhs,const HugeNatural& rhs)
{
    if(rhs.IsZero() || lhs.IsLessThan(rhs))
        return lhs;
    if(rhs.IsEqual(1) || rhs.IsEqual(lhs) || lhs.IsZero())
    {
        lhs.SetZero();
        lhs.m_bc=1;
        return lhs;
    }

    HugeNatural tmp = lhs;
    tmp/=rhs;
    lhs-=(tmp*rhs);
    return lhs;
}

// Konstante, die bei Eingabe / Ausgabe die Größe des char-Arrays festlegt.
/* Nicht ändern */ const size_t HUGE_FACTOR = 5; // Nicht ändern !!

// Ausgabe / Eingabe
std::ostream& operator<<(std::ostream& os,const HugeNatural& hn)
{
    if(hn.m_bc<=2)
    {
        os << hn.Long();
        return os;
    }
    HugeNatural tmp = hn;
    unsigned char outp[HUGE_MAX * HUGE_FACTOR];
    size_t array_size = 0;

    // Ins Dezimalsystem umwandeln
    for(size_t i=0;tmp>9;++i)
    { // i-te Ziffer ist der Rest bei Division durch 10
        outp[i] = (unsigned char) (tmp%10).Short();
        tmp/=10;
    }
    outp[i] = (unsigned char) tmp.Short();
    ++i;

    // Ausgabe
    for(;;)
    {
        if(i==0)
            break;
        os << (char)(outp[--i]+'0');
    }

    return os;
}

std::istream& operator>>(std::istream& is, HugeNatural& hn)
{
    unsigned char inp[HUGE_MAX * HUGE_FACTOR];
    char input;
    HugeNatural ten(1); // ten speichert die Potenzen von 10

    hn.SetZero();
    hn.m_bc = 1;

    // Eingabe
    for(size_t i=0;i<(HUGE_MAX * HUGE_FACTOR);++i)
    {
        is.get(input); // Ziffer einlesen
        if((input<'0')||(input>'9'))
            break;
        inp[i] = input-'0';
    }

    // In HugeNatural konvertieren
    for(;;)
    {
        if(i==0)
            break;
        hn+=(inp[--i]*ten); // Zeichen wird berechnet und mit ten multipliziert         
        ten*=10; // Potenz von 10 um 1 erhöhen
    }   
    return is;
}

#endif // HUGENAT_HPP

Doktor Prokt: Vergleich bitte mal die Geschwindigkeit mit deinem Datentyp.

[ Dieser Beitrag wurde am 12.12.2002 um 16:21 Uhr von Gary editiert. ]

Gary

Jetzt hab ich doch glatt die Bit-Funktionen vergessen:

// Name:
//      bitalg.h

// Inhalt:
//      Funktionen zur Bit-Arithmetik.

// Autor:
//      Gernot Fritz (2002)

// Namespace:
//      bit

#ifndef BITALG_HPP
#define BITALG_HPP

// Hinweis: Die Funktionen befinden sich im namespace "bit"

namespace bit {

// Prüfen, ob n-tes Bit in x gesetzt ist
inline bool IsSet(unsigned long x, unsigned char n)
{
    if(x & (1 << n))
        return true;
    return false;
}

// n-tes Bit in x setzen
inline void Set(unsigned long &x, unsigned char n)
{
    x = x | (1 << n);
}

// n-tes Bit in x löschen
inline void Clear(unsigned long &x, unsigned char n)
{
    x = x & ~(1 << n);
}

// n-tes Bit in x invertieren
inline void Invert(unsigned long &x, unsigned char n)
{
    x = x ^ (1 << n);
}

// Prüfen, ob n-tes Bit in x gesetzt ist
inline unsigned char IsSet(unsigned short x, unsigned char n)
{
    if(x & (1 << n))
        return true;
    return false;
}

// n-tes Bit in x setzen
inline void Set(unsigned short &x, unsigned char n)
{
    x = x | (1 << n);
}

// n-tes Bit in x löschen
inline void Clear(unsigned short &x, unsigned char n)
{
    x = x & ~(1 << n);
}

// n-tes Bit in x invertieren
inline void Invert(unsigned short &x, unsigned char n)
{
    x = x ^ (1 << n);
}

// x an der Stelle n cracken und ab dieser Stelle alle niederwertigen Bits in
// ul speichern und zurückgeben
unsigned long Crack(unsigned long x, unsigned char n)
{
    unsigned long ul = 0;
    for(unsigned char i=0;i<=n;++i)
    {
        if(x & (1 << i)) // Prüfen, ob i-tes Bit in x gesetzt ist
            ul = ul | (1 << i); // Wenn ja, dann i-tes Bit in ul setzen
    }
    return ul;
}

// die ersten 16 Bit zurückgeben
inline unsigned short Part1(unsigned long ul)
{
    return (unsigned short)ul;
}

// Bit 16-31 zurückgeben
inline unsigned short Part2(unsigned long ul)
{
    ul>>=16; // um 16 Stellen nach rechts shiften
    return (unsigned short)ul;
}

} // namespace "bit"

#endif // BITALG_HPP