64-битный integer из двух 32-битных / LongLong

@GoldenId · Регистрация: 11.11.2010

Author24 — интернет-сервис помощи студентам

Написал тут по просьбе велосипед для 64-битной арифметики на основе двух 32-битных чисел. Прошу критику. В т.ч. по стилю (идентификаторы). Сам отметил актуальные к правке места todo.

longlong.h

C++

#ifndef LONGLONG_H_INCLUDED
#define LONGLONG_H_INCLUDED
#include <iostream>
#include <string>
#include <limits>
 
class LongLong
{
public:
    typedef unsigned long low_type;
    typedef long high_type;
    typedef unsigned long unsigned_low_type;
    typedef unsigned long unsigned_high_type;
 
    static const int high_digits
        = std::numeric_limits<high_type>::digits
        + (int) std::numeric_limits<high_type>::is_signed;
    static const int low_digits
        = std::numeric_limits<low_type>::digits
        + (int) std::numeric_limits<low_type>::is_signed;
    static const int all_digits
        = high_digits + low_digits;
 
private:
    low_type _low;
    high_type _high;
public:
    LongLong() {}
    LongLong( const LongLong& other ) : _low( other._low ), _high( other._high ) {}
    LongLong( high_type high, low_type low ) : _low( low ), _high( high ) {}
    LongLong operator - () const;
    LongLong operator = ( const LongLong& right );
    LongLong operator + ( const LongLong& right ) const;
    LongLong operator += ( const LongLong& right );
    LongLong operator - ( const LongLong& right ) const;
    LongLong operator -= ( const LongLong& right );
    LongLong operator * ( const LongLong& right ) const;
    LongLong operator *= ( const LongLong& right );
    LongLong operator / ( const LongLong& right ) const;
    LongLong operator /= ( const LongLong& right );
    LongLong operator % ( const LongLong& right ) const;
    LongLong operator %= ( const LongLong& right );
    LongLong operator << ( unsigned int s ) const;
    LongLong operator <<= ( unsigned int s );
    LongLong operator >> ( unsigned int s ) const;
    LongLong operator >>= ( unsigned int s );
    bool operator == ( const LongLong& right ) const;
    bool operator != ( const LongLong& right ) const;
    bool operator >= ( const LongLong& right ) const;
    bool operator <= ( const LongLong& right ) const;
    bool operator > ( const LongLong& right ) const;
    bool operator < ( const LongLong& right ) const;
    // совмещённая функция для вычисления сразу частного и остатка от деления
    static void divMod( LongLong left, LongLong right, LongLong& quot, LongLong& rem );
    friend std::ostream& operator << ( std::ostream& ostr, const LongLong& ll );
protected:
    std::string toStringBin( bool postfix ) const;
    std::string toStringDec() const;
    std::string toStringHex( bool prefix ) const;
    static const LongLong c_zero;
    static const LongLong c_one;
    static const LongLong c_minus_one;
    static const LongLong c_ten;
};
#endif // LONGLONG_H_INCLUDED

longlong.cpp

C++

#ifndef LONGLONG_CPP_INCLUDED
#define LONGLONG_CPP_INCLUDED
#include <stdexcept>
#include <string>
#include <algorithm>
#include "longlong.h"
 
const LongLong LongLong::c_zero         = LongLong( 0, 0 );
const LongLong LongLong::c_one          = LongLong( 0, 1 );
const LongLong LongLong::c_minus_one    = -LongLong::c_one;
const LongLong LongLong::c_ten          = LongLong( 0, 10 );
 
LongLong LongLong::operator - () const
{
    return LongLong( ~_high, ~_low ) + c_one;
}
 
LongLong LongLong::operator = ( const LongLong& right )
{
    _low = right._low;
    _high = right._high;
    return *this;
}
 
LongLong LongLong::operator + ( const LongLong& right ) const
{
    low_type low = _low + right._low;
    high_type high = _high + right._high;
    // обработка переполнений
    if( low < _low )
        high++;
    return LongLong( high, low );
}
 
LongLong LongLong::operator += ( const LongLong& right )
{
    return *this = *this + right;
}
 
LongLong LongLong::operator - ( const LongLong& right ) const
{
    low_type low = _low - right._low;
    high_type high = _high - right._high;
    // обработка переполнений
    if( _low < right._low )
        high--;
    return LongLong( high, low );
}
 
LongLong LongLong::operator -= ( const LongLong& right )
{
    return *this = *this - right;
}
 
LongLong LongLong::operator * ( const LongLong& right ) const
{
    LongLong res( c_zero );
    low_type lm = 1;
    for( int d = 0; d < low_digits; d++, lm <<= 1 )
        if( _low & lm )
            res += right << d;
 
    high_type hm = 1;
    for( int d = low_digits; d < all_digits; d++, hm <<= 1 )
        if( _high & hm )
            res += right << d;
    return res;
}
 
LongLong LongLong::operator *= ( const LongLong& right )
{
    return *this = *this * right;
}
 
LongLong LongLong::operator / ( const LongLong& right ) const
{
    LongLong quot, rem;
    divMod( *this, right, quot, rem );
    return quot;
}
 
LongLong LongLong::operator /= ( const LongLong& right )
{
    return *this = *this / right;
}
 
LongLong LongLong::operator % ( const LongLong& right ) const
{
    LongLong quot, rem;
    divMod( *this, right, quot, rem );
    return rem;
}
 
LongLong LongLong::operator %= ( const LongLong& right )
{
    return *this = *this % right;
}
 
LongLong LongLong::operator << ( unsigned int s ) const
{
    // сдвиг на 32 и больше бит может работать неправильно
    high_type high1 = _high << s;
    high_type high2 = ( unsigned_low_type )_low >> ( low_digits - s );
    low_type low = _low << s;
 
    // todo: opt
    if( high_digits == 32 && s >= 32 )
        high1 = 0;
    if( low_digits == 32 )
    {
        if( s >= 32 )
            low = 0;
        if( low_digits >= s + 32 )
            high2 = 0;
        else if( s > low_digits )
            high2 = ( unsigned_low_type )_low << ( s - low_digits );
    }
    return LongLong( high1 | high2, low );
}
 
LongLong LongLong::operator <<= ( unsigned int s )
{
    return *this = *this << s;
}
 
LongLong LongLong::operator >> ( unsigned int s ) const
{
    // сдвиг на 32 и больше бит может работать неправильно
    high_type high = _high >> s;
    low_type low1 = _high << ( low_digits - s );
    low_type low2 = ( unsigned_low_type )_low >> s;
 
    // todo: opt
    if( high_digits == 32 && s >= 32 )
        high = ( high < 0 ) ? -1 : 0;
    if( low_digits == 32 )
    {
        if( low_digits < s )
            low1 = _high >> ( s - low_digits );
        if( s >= 32 )
            low2 = 0;
    }
    return LongLong( high, low1 | low2 );
}
 
LongLong LongLong::operator >>= ( unsigned int s )
{
    return *this = *this >> s;
}
 
bool LongLong::operator == ( const LongLong& right ) const
{
    return _high == right._high && _low == right._low;
}
 
bool LongLong::operator != ( const LongLong& right ) const
{
    return _high != right._high || _low != right._low;
}
 
bool LongLong::operator >= ( const LongLong& right ) const
{
    if( _high > right._high )
        return true;
    if( _high < right._high )
        return false;
    return _low >= right._low;
}
 
bool LongLong::operator <= ( const LongLong& right ) const
{
    if( _high < right._high )
        return true;
    if( _high > right._high )
        return false;
    return _low <= right._low;
}
 
bool LongLong::operator > ( const LongLong& right ) const
{
    if( _high > right._high )
        return true;
    if( _high < right._high )
        return false;
    return _low > right._low;
}
 
bool LongLong::operator < ( const LongLong& right ) const
{
    if( _high < right._high )
        return true;
    if( _high > right._high )
        return false;
    return _low < right._low;
}
 
std::string LongLong::toStringBin( bool postfix ) const
{
    std::string s;
    unsigned_high_type hm = 1 << ( high_digits - 1 );
    unsigned_low_type  lm = 1 << (  low_digits - 1 );
    for( int d = high_digits - 1; d >= 0; d--, hm >>= 1 )
        s += ( ( (unsigned_high_type)_high & hm ) != 0 ) ? '1' : '0';
 
    for( int d = low_digits - 1; d >= 0; d--, lm >>= 1 )
        s += ( ( (unsigned_low_type)_low & lm ) != 0 ) ? '1' : '0';
    return s + ( postfix ? "b" : "" );
}
 
std::string LongLong::toStringHex( bool prefix ) const
{
    static char hexs[] = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F' };
    int lhexs =  low_digits / 4;
    int hhexs = high_digits / 4;
    unsigned_high_type hm = 0xf << ( high_digits - 4 );
    unsigned_low_type  lm = 0xf << (  low_digits - 4 );
 
    std::string s( prefix ? "0x" : "" );
    for( int h = 4*( hhexs - 1 ); h >= 0; h -= 4, hm >>= 4 )
        s += hexs[( (unsigned_high_type)_high & hm ) >> h];
 
    for( int h = 4*( lhexs - 1 ); h >= 0; h -= 4, lm >>= 4 )
        s += hexs[( (unsigned_low_type)_low & lm ) >> h];
    return s;
}
 
std::string LongLong::toStringDec() const
{
    if( _high == 0 && _low == 0 )
        return "0";
    std::string s;
 
    // проход от младших к старшим нужен, чтобы правильно обрабатывать старший разряд (0x80000000_00000000)
    bool neg = *this < c_zero;
    LongLong a( *this ); //neg ? -*this : *this;
    LongLong d;
    while( a != c_zero )
    {
        divMod( a, c_ten, a, d );
        //d = neg ? ( - ( a % c_ten ) ) : ( a % c_ten );//!neg ? ( a - ( a / c_ten ) * c_ten ) : ( ( a / c_ten ) * c_ten - a );
        //d = ( neg ? ( -d ) : d );
        s += std::to_string( ( neg ? ( -d ) : d )._low );
        //a /= c_ten;   // todo: opt
    }
    s += neg ? "-" : "";
    std::reverse( s.begin(), s.end() );
    return s;
}
 
// совмещённая функция для вычисления сразу частного и остатка от деления
void LongLong::divMod( LongLong left, LongLong right, LongLong& quot, LongLong& rem )
{
    if( right == c_zero )
        throw std::runtime_error( "Division by zero" );
 
    rem = left;                 // остаток
    quot = c_zero;              // частное
    LongLong rr = rem >> 1;     // для точного определения максимального скользящего делителя
    LongLong div = right;       // скользящий делитель
    LongLong m;                 // маска
    int sh = 0;                 // сдвиг
    // в этом алгоритме нельзя брать -left, -right из-за значения 0x8000000000000000,
    // обратное которому не влезает в наш LongLong,
    // поэтому приходится расписывать 4 ветви:
    if( rem >= c_zero )
    {
        if( div > c_zero )
        {
            m = c_one;
            // проход вверх для поиска максимального скользящего делителя
            while( div < rr )
            {
                div <<= 1;
                m <<= 1;
                sh++;
            }
            // проход вниз с нисходящим делением
            while( sh >= 0 )
            {
                if( rem >= div )
                {
                    rem -= div;
                    quot += m;
                }
                div >>= 1;
                m >>= 1;
                sh--;
            }
        } else // if( div < 0 )
        {
            // то же самое, только для других знаков
            m = c_minus_one;
            while( c_zero < rr + div )
            {
                div <<= 1;
                m <<= 1;
                sh++;
            }
            while( sh >= 0 )
            {
                if( rem + div >= c_zero )
                {
                    rem += div;
                    quot += m;
                }
                div >>= 1;
                m >>= 1;
                sh--;
            }
        }
    } else // if( rem < 0 )
    {
        // то же самое, только для других знаков
        if( div > c_zero )
        {
            m = c_minus_one;
            while( rr + div < c_zero )
            {
                div <<= 1;
                m <<= 1;
                sh++;
            }
            while( sh >= 0 )
            {
                if( c_zero >= rem + div )
                {
                    rem += div;
                    quot += m;
                }
                div >>= 1;
                m >>= 1;
                sh--;
            }
        } else // if( div < 0 )
        {
            m = c_one;
            while( div > rr )
            {
                div <<= 1;
                m <<= 1;
                sh++;
            }
            while( sh >= 0 )
            {
                if( rem <= div )
                {
                    rem -= div;
                    quot += m;
                }
                div >>= 1;
                m >>= 1;
                sh--;
            }
        }
    }
}
 
std::ostream& operator << ( std::ostream& ostr, const LongLong& ll )
{
    std::ios::fmtflags fs = ostr.flags();
    if( fs & std::ios::hex )
        ostr << ll.toStringHex( ostr.flags() & ostr.showbase );
    else if( fs & std::ios::dec )
        ostr << ll.toStringDec();
    else if( fs & std::ios::oct )       // при настройке потока на вывод восьмеричных чисел
        ostr << ll.toStringBin( ostr.flags() & ostr.showbase );     // выводится двоичное представление
    else
        throw std::runtime_error( "Unknown base" );
    return ostr;
}
 
#endif // LONGLONG_CPP_INCLUDED

main.cpp

C++

#include <iostream>
#include <iomanip>
#include "longlong.h"
 
int main()
{
    std::cout << std::showbase;
    std::cout << LongLong( 0x80000000, 0x00 ) << "\n";
 
    LongLong ll1( 0x00000000, 0x00000000 );
    LongLong ll2( 0xffffffff, 0xffffffff );
    LongLong ll3( 0x00000000, 0x00000001 );
    LongLong ll4 = ll1 + ll2 + ll3;
    LongLong ll5 = ll1 - ll2;
    std::cout << "In binary mode:\n" << std::oct;
    std::cout << "LongLong1: " << ll1 << "\n";
    std::cout << "LongLong2: " << ll2 << "\n";
    std::cout << "LongLong3: " << ll3 << "\n";
    std::cout << "LongLong4: " << ll4 << "\n";
    std::cout << "LongLong5: " << ll5 << "\n";
    std::cout << "In heximal mode:\n" << std::hex;
    std::cout << ll3 << " - " << ll2 << ": " << ll3 - ll2 << "\n";
    std::cout << ll2 << " - " << ll3 << ": " << ll2 - ll3 << "\n";
    LongLong ll6( 0xffffffff, 0x0 );
    LongLong ll7( 0x0, 0xffffffff );
    std::cout << ll6 << " + " << ll7 << ": " << ll6 + ll7 << "\n";
    std::cout << ll6 << " - " << ll7 << ": " << ll6 - ll7 << "\n";
    std::cout << ll7 << " - " << ll6 << ": " << ll7 - ll6 << "\n";
 
    std::cout << "0xff00 - 0x00ff: " << short(0xff00) - short(0x00ff) << "\n";
    std::cout << "0x00ff - 0xff00: " << short(0x00ff) - short(0xff00) << "\n";
    std::cout << "0x0103 * 0x0102: " << short(0x0103)*short(0x0102) << "\n";
 
    LongLong ll11( 0x1, 0x03 );
    LongLong ll12( 0x1, 0x02 );
    std::cout << ll11 << " * " << ll12 << ": " << ll11*ll12 << "\n";
 
    std::cout << ll11 << " << 1 :" << ( ll11 << 1 ) << "\n";
    std::cout << "In decimal mode:\n" << std::dec << std::boolalpha;
 
    LongLong ll13( 0xffffffff, 0xfffffffd );
    LongLong ll14( 0xffffffff, 0xfffffffe );
    std::cout << ll13 << " * " << ll14 << ": " << ll13*ll14 << "\n";
 
    std::cout << ll11 << " == " << ll12 << ": " << ( ll11 == ll12 ) << "\n";
    std::cout << ll12 << " != " << ll13 << ": " << ( ll12 != ll13 ) << "\n";
    std::cout << ll13 << " <= " << ll14 << ": " << ( ll13 <= ll14 ) << "\n";
    std::cout << ll12 << " <= " << ll13 << ": " << ( ll12 <= ll13 ) << "\n";
    std::cout << ll14 << " <= " << ll12 << ": " << ( ll14 <= ll12 ) << "\n";
    std::cout << ll13 << " >= " << ll14 << ": " << ( ll13 >= ll14 ) << "\n";
    std::cout << ll12 << " >= " << ll13 << ": " << ( ll12 >= ll13 ) << "\n";
    std::cout << ll14 << " >= " << ll12 << ": " << ( ll14 >= ll12 ) << "\n";
 
    LongLong ll21( 0, 0x10 );
    LongLong ll22( 0, 0x05 );
    std::cout << ll21 << "/" << ll22 << ": " << ll21/ll22 << "\n";
 
    std::cout << LongLong( 0x80000000, 0x0 ) << "\n";
 
    LongLong ll31( 0, 36 ); 
    LongLong ll32( 0, 5 );
    std::cout <<  ll31 << "/" <<  ll32 << ": " <<  ll31 /  ll32 << "\n";
    std::cout << -ll31 << "/" <<  ll32 << ": " << -ll31 /  ll32 << "\n";
    std::cout << -ll31 << "/" << -ll32 << ": " << -ll31 / -ll32 << "\n";
    std::cout <<  ll31 << "/" << -ll32 << ": " <<  ll31 / -ll32 << "\n";
    std::cout <<  ll31 << "%" <<  ll32 << ": " <<  ll31 %  ll32 << "\n";
    std::cout << -ll31 << "%" <<  ll32 << ": " << -ll31 %  ll32 << "\n";
    std::cout << -ll31 << "%" << -ll32 << ": " << -ll31 % -ll32 << "\n";
    std::cout <<  ll31 << "%" << -ll32 << ": " <<  ll31 % -ll32 << "\n";
 
    LongLong left( 0, 20 ), right( 0, 3 );//, quot, rem;
    LongLong::divMod( left, right, left, right );
    std::cout << left << ", " << right << "\n";
 
 
    std::cin.get();
    return 0;
}

	19.04.2017, 12:22