/*! @file @brief 多倍長整数クラステンプレート静的に桁を設定できる多倍長整数クラステンプレート実装は"MultiInteger.hpp" @author Juna */ #ifndef Juna_Multi_Integer_H #define Juna_Multi_Integer_H namespace Juna { //! 多倍長整数クラステンプレート /*! 静的に桁を設定できる基本は符号無し多倍長整数クラステンプレート @param Figure 桁数 @param UDigitType 一桁の型 @param UDigit2Type 計算用の型 @pre (Figure >= 2) && (Figure * sizeof(UDigitType) >= 4) && (sizeof(UDigit2Type) / sizeof(UDigitType) >= 2) */ template class MultiInteger { public: typedef UDigitType digit_t; typedef UDigit2Type digit2_t; typedef MultiInteger MyType; typedef MultiInteger DoubleType; enum {digit_bit = sizeof(digit_t) * 8}; typedef int int32; typedef unsigned int uint32; typedef unsigned char byte; // 公開 digit_t Digit[Figure]; public: /*****************************************************************************/ //! @name コンストラクタ //@{ //! 初期化しないコンストラクタ MultiInteger(void) {} //! 0初期化コンストラクタ指定型 struct zero_init{}; //! 0初期化コンストラクタ MultiInteger(zero_init) {Clear();} MultiInteger(digit2_t n) {*this = n;} //!< 整数値で初期化 MultiInteger(int32 n) {*this = n;} //!< 整数値で初期化 MultiInteger(uint32 n) {*this = n;} //!< 整数値で初期化 //! 文字列で初期化 MultiInteger(const char *string) {*this = string;} //! 異なる桁を無理矢理コピーコンストラクタ template explicit MultiInteger(const MultiInteger &src) {Assign(src);} //! コピーコンストラクタ MultiInteger(const MyType &src) {*this = src;} //! 何か演算するコンストラクタ template MultiInteger(Operation op,const MyType &src) {op(*this,src);} //! 2値から何か演算するコンストラクタ template MultiInteger(Operation op,const MyType &lhs,const MyType &rhs) {op(*this,lhs,rhs);} //! 2値から何か演算するコンストラクタ template MultiInteger(Operation op,const MyType &lhs,int rhs) {op(*this,lhs,rhs);} //@} /*****************************************************************************/ //! @name 代入 //@{ //! 初期化（0代入） void Clear(void) { for (int i = 0;i < Figure;i++) Digit[i] = 0; return; // 念のためサイズチェック int static_assert[sizeof(digit2_t) / sizeof(digit_t) >= 2] = {0}; } MyType &AssignDecimal(const char *string); //!< 符号無し十進文字列代入 MyType &AssignHex(const char *string); //!< 十六進文字列代入 MyType &AssignOctal(const char *string); //!< 八進文字列代入 MyType &AssignBinary(const char *string); //!< 二進文字列代入 MyType &AssignSignedDecimal(const char *string);//!< 符号付き十進文字列代入 //! 任意桁代入 template MyType &Assign(const MultiInteger &rhs) { if (RHSFigure < Figure) return AssignArray(rhs.Digit,RHSFigure); for (int i = 0;i < Figure;i++) Digit[i] = rhs[i]; return *this; } //! 符号付き任意桁代入 template MyType &AssignSigned(const MultiInteger &rhs) { if (RHSFigure < Figure) return AssignSignedArray(rhs.Digit,RHSFigure); return Assign(rhs); } //@} /*****************************************************************************/ //! @name 代入演算子 //@{ //! 任意桁代入 template MyType &operator=(const MultiInteger &rhs) { return Assign(rhs); // 桁が失われる可能性のある代入はこの関数では禁止 int static_assert[RHSFigure <= Figure]; } MyType &operator=(digit2_t rhs); //!< 数値型代入 MyType &operator=(uint32 rhs); //!< 符号無し32bit値代入 MyType &operator=(int32 rhs); //!< 符号付き32bit値代入 //! 文字列代入 /*! 符号無しの、10進か"0x"or"0X"で始まる16進 */ MyType &operator=(const char *rhs) { if (rhs[0] == '0' && (rhs[1] == 'x' || rhs[1] == 'X')) AssignHex(rhs); else AssignDecimal(rhs); return *this; } //@} /*****************************************************************************/ //! @name 演算代入演算子 //@{ MyType &operator+=(const MyType &rhs) {Add(*this,*this,rhs);return *this;} MyType &operator-=(const MyType &rhs) {Subtract(*this,*this,rhs);return *this;} MyType &operator*=(const MyType &rhs) { MyType tmp; Multiply(tmp,*this,rhs); return *this = tmp; } MyType &operator/=(const MyType &rhs) {Divide(*this,*this,rhs);return *this;} MyType &operator%=(const MyType &rhs) {Modulo(*this,*this,rhs);return *this;} MyType &operator<<=(int n) {ShiftLeft(*this,*this,n);return *this;} MyType &operator>>=(int n) {ShiftRight(*this,*this,n);return *this;} MyType &operator&=(const MyType &rhs) {BitAnd(*this,*this,rhs);return *this;} MyType &operator|=(const MyType &rhs) {BitOr(*this,*this,rhs);return *this;} MyType &operator^=(const MyType &rhs) {BitXor(*this,*this,rhs);return *this;} //@} /*****************************************************************************/ //! @name 単項演算子 //@{ MyType &operator++(void) {Increment(*this,*this);return *this;} MyType operator++(int) {MyType ret(*this);Increment(*this,*this);return ret;} MyType &operator--(void) {Decrement(*this,*this);return *this;} MyType operator--(int) {MyType ret(*this);Decrement(*this,*this);return ret;} MyType operator-(void) const {return MyType(Negate,*this);} MyType operator~(void) const {return MyType(BitNot,*this);} const MyType &operator+(void) const {return *this;} //! n = -n MyType &SetNegative(void) {Negate(*this,*this);return *this;} //! n = ~n MyType &SetBitNot(void) {BitNot(*this,*this);return *this;} //@} /*****************************************************************************/ //! @name 異なる桁とも可能な符号無し比較演算子 //@{ template bool operator==(const MultiInteger &rhs) const {return Compare(rhs) == 0;} template bool operator!=(const MultiInteger &rhs) const {return Compare(rhs) != 0;} template bool operator>(const MultiInteger &rhs) const {return Compare(rhs) > 0;} template bool operator<(const MultiInteger &rhs) const {return Compare(rhs) < 0;} template bool operator>=(const MultiInteger &rhs) const {return Compare(rhs) >= 0;} template bool operator<=(const MultiInteger &rhs) const {return Compare(rhs) <= 0;} //@} /*****************************************************************************/ //! @name 二項演算子 //@{ friend MyType operator+(const MyType &lhs,const MyType &rhs) {return MyType(Add,lhs,rhs);} friend MyType operator-(const MyType &lhs,const MyType &rhs) {return MyType(Subtract,lhs,rhs);} friend MyType operator*(const MyType &lhs,const MyType &rhs) {return MyType(Multiply,lhs,rhs);} friend MyType operator/(const MyType &lhs,const MyType &rhs) {return MyType(Divide,lhs,rhs);} friend MyType operator%(const MyType &lhs,const MyType &rhs) {return MyType(Modulo,lhs,rhs);} friend MyType operator<<(const MyType &lhs,int rhs) {return MyType(ShiftLeft,lhs,rhs);} friend MyType operator>>(const MyType &lhs,int rhs) {return MyType(ShiftRight,lhs,rhs);} friend MyType operator&(const MyType &lhs,const MyType &rhs) {return MyType(BitAnd,lhs,rhs);} friend MyType operator|(const MyType &lhs,const MyType &rhs) {return MyType(BitOr,lhs,rhs);} friend MyType operator^(const MyType &lhs,const MyType &rhs) {return MyType(BitXor,lhs,rhs);} //@} /*****************************************************************************/ //! @name 符号無し比較演算子 //@{ friend bool operator==(const MyType &lhs,const MyType &rhs) {return lhs.Compare(rhs) == 0;} friend bool operator!=(const MyType &lhs,const MyType &rhs) {return lhs.Compare(rhs) != 0;} friend bool operator>(const MyType &lhs,const MyType &rhs) {return lhs.Compare(rhs) > 0;} friend bool operator<(const MyType &lhs,const MyType &rhs) {return lhs.Compare(rhs) < 0;} friend bool operator>=(const MyType &lhs,const MyType &rhs) {return lhs.Compare(rhs) >= 0;} friend bool operator<=(const MyType &lhs,const MyType &rhs) {return lhs.Compare(rhs) <= 0;} //@} /*****************************************************************************/ //! @name 演算関数 //@{ //! 足し算 /*! @return carry */ static bool Add(MyType &dest,const MyType &lhs,const MyType &rhs); //! インクリメント static bool Increment(MyType &dest,const MyType &src); //! 引き算 /*! @return borrow */ static bool Subtract(MyType &dest,const MyType &lhs,const MyType &rhs); //! デクリメント static bool Decrement(MyType &dest,const MyType &src); //! 掛け算 /*! @pre &dest != &lhs && &dest != &rhs */ static void Multiply(MyType &dest,const MyType &lhs,const MyType &rhs); //! 二倍の桁の型を返して桁あふれしない掛け算 static void MultiplyEx(DoubleType &dest,const MyType &lhs,const MyType &rhs); //! 二倍の桁の型を返して桁あふれしない符号付き掛け算 static void SignedMultiplyEx(DoubleType &dest,const MyType &lhs,const MyType &rhs); //! 符号無し割り算 /*! @ref DivideEx() */ static void Divide(MyType &dest,const MyType &lhs,const MyType &rhs) {DivideEx(dest,MyType(),lhs,rhs);} //! 符号無し割り算の剰余 /*! @ref DivideEx() */ static void Modulo(MyType &dest,const MyType &lhs,const MyType &rhs) {DivideEx(MyType(),dest,lhs,rhs);} //! 符号付き割り算 /*! @ref DivideEx() */ static void SignedDivide(MyType &dest,const MyType &lhs,const MyType &rhs) {SignedDivideEx(dest,MyType(),lhs,rhs);} //! 符号付き割り算の剰余 /*! @ref DivideEx() */ static void SignedModulo(MyType &dest,const MyType &lhs,const MyType &rhs) {SignedDivideEx(MyType(),dest,lhs,rhs);} //! 符号無し割り算 /*! @param[out] quotient 商 @param[out] remainder 余り @param[in] dividend 被除数 @param[in] divisor 除数 @pre &divisor != "ient && &divisor != &remainder && divisor != 0 @pre "ient != &remainder */ static void DivideEx(MyType "ient,MyType &remainder,const MyType ÷nd,const MyType &divisor); //! 符号付き割り算 /*! @ref Divide() */ static void SignedDivideEx(MyType "ient,MyType &remainder,const MyType ÷nd,const MyType &divisor); //! 左シフト /*! マイナス方向は未定義 */ static void ShiftLeft(MyType &dest,const MyType &lhs,int rhs); //! 論理右シフト /*! マイナス方向は未定義 */ static void ShiftRight(MyType &dest,const MyType &lhs,int rhs); //! 算術右シフト /*! マイナス方向は未定義 */ static void ArithmeticShiftRight(MyType &dest,const MyType &lhs,int rhs); //! ２の補数 static void Negate(MyType &dest,const MyType &src); //! ビット反転（１の補数） static void BitNot(MyType &dest,const MyType &src); //! ビットごとの論理積 static void BitAnd(MyType &dest,const MyType &lhs,const MyType &rhs); //! ビットごとの論理和 static void BitOr(MyType &dest,const MyType &lhs,const MyType &rhs); //! ビットごとの排他的論理和 static void BitXor(MyType &dest,const MyType &lhs,const MyType &rhs); //@} /*****************************************************************************/ //! @name 比較演算関数 //@{ //! 比較 template int Compare(const MultiInteger &rhs) const {return Compare(Digit,GetFigure(),rhs.Digit,rhs.GetFigure());} //! 符号付き比較 template int SignedCompare(const MultiInteger &rhs) const { bool minus = isMinus(),rhs_minus = rhs.isMinus(); if (minus ^ rhs_minus) return rhs_minus - minus; return Compare(rhs) * (!minus - minus); } //@} /*****************************************************************************/ //! @name 参照 //@{ //! 0かどうか bool isZero(void) const {return GetFigure() == 0;} //! マイナスかどうか bool isMinus(void) const {return (Digit[Figure-1] >> (digit_bit - 1)) & 1;} //! 有効桁数 int GetFigure(void) const { int i; for (i = Figure - 1;i >= 0 && Digit[i] == 0;i--) ; return i+1; } //! 符号付き有効桁数 int GetFigureSigned(void) const { int i; for (i = Figure - 1;i > 0 && Digit[i] == 0xFF;i--) ; return i+1; } //! []による格納値参照 digit_t operator[](int figure) const {return Digit[figure];} //@} /*****************************************************************************/ //! @name Byte単位参照 //@{ int GetByteFigure(void) const; byte GetByteDigit(int figure) const {return byte(Digit[figure / sizeof(digit_t)] >> ((figure & sizeof(digit_t) - 1) * 8));} void SetByteDigit(int figure,byte set) { const int fs = figure / sizeof(digit_t); const int bs = (figure & (sizeof(digit_t) - 1)) * 8; Digit[fs] = (Digit[fs] & ~(0xFF << bs)) | (set << bs); } //@} /*****************************************************************************/ //! @name 整数値参照 //@{ uint32 GetUInt32(void) const { if (sizeof(digit_t) == 1) return Digit[0] | (Digit[1] << 8) | (Digit[2] << 16) | (Digit[3] << 24); if (sizeof(digit_t) == 2) return Digit[0] | (Digit[1] << 16); return Digit[0]; } int32 GetInt32(void) const {return int32(GetUInt32());} digit2_t GetDigit2(void) const {return Digit[0] | (digit2_t(Digit[1]) << digit_bit);} //@} /*****************************************************************************/ //! @name 文字列参照 //@{ //! 十進数文字列化 /*! @param[out] buf 文字列を受け取る十分な大きさのバッファ @param comma ３桁ごとのコンマ区切りを入れるかどうか @return bufを返す */ char *toDecimalString(char *buf,bool comma = false) const; //! 符号付き十進数文字列化 char *toSignedDecimalString(char *buf,bool comma = false) const { if (!isMinus()) return toDecimalString(buf,comma); *buf = '-'; (-*this).toDecimalString(buf+1,comma); return buf; } //! static バッファを用いた十進数文字列化 const char *GetString(bool signed_ = false) const; //@} /*****************************************************************************/ private: // 配列代入 /* @pre size <= Figure */ MyType &AssignArray(const digit_t *digit,int size); MyType &AssignSignedArray(const digit_t *digit,int size); // 桁上がり代入 static digit_t SetDigit(digit_t &digit,digit2_t set) { digit = digit_t(set); return digit_t(set >> digit_bit); } // 比較 static int Compare(const digit_t *lhs_digit,int lhs_figure, const digit_t *rhs_digit,int rhs_figure) { if (lhs_figure != rhs_figure) return lhs_figure - rhs_figure; for (int i = lhs_figure - 1;i >= 0;i--) if (lhs_digit[i] != rhs_digit[i]) return (lhs_digit[i] > rhs_digit[i]) - (lhs_digit[i] < rhs_digit[i]); return 0; } }; }//namespace Juna #endif