NxBigInt 클래스 설계

사실 오래전에 짰던 소스이기는 한데, 요즘 프로젝트 오일러 문제를 풀다보니, BigInt를 사용해야할 경우가 많이 있네요.  그래서 최근에 다시 수정을 해보았습니다.

이 라이브러리는 다음과 같은 것을 중점적으로 처리하도록 일단 설계했습니다.

1. 여러가지 부분에서 효율적으로 사용할 수 있는 기능을 구현한다.

    예를 들어서 라이브러리를 일반 연산자 오버로딩만을 이용할 경우 오브젝트를 복사해야하는 일들이 많이 발생합니다.  이런 것을 하지 않아도 될 수 있는 기능들을 많이 마련하도록 하였습니다.

2. 보안 등에 사용할 수 있는 기능 추가.

    일반적인 수식 계산보다는 비트 연산 등을 처리할 수 있도록 설계하고자 하였습니다.  아직은 미약한 부분들이 많습니다만.

그래서 만들어진 자료구조형은 다음과 같습니다.

할당을 받은 크기는 m_nSize 변수에 저장이 됩니다.  데이터 크기에 꼭맞게 할당을 하지 않고, 여유롭게 할당을 하도록 하였습니다.  m_nSize 자체를 4씩 늘게 하였습니다.  현재 32비트 자료형을 사용하기 때문에 저장할 수 있는 단위는 128비트씩 늘게 됩니다.  128비트는 10의 38승정도를 저장할 수 있습니다.  (왠만한 보안키가 512비트, 1024비트인 것을 감안한다면, 이정도 단위로 할당을 주면, 왠만한 계산을 해도 재할당을 받지 않아도 됩니다.)  재할당을 받는 연산이 상당히 비싼 작업입니다.  새로운 데이터 공간을 할당받고, 기존 데이터를 복사해야하기 때문입니다.  그래서 재할당이 빈번하게 발생하면 안 된다고 생각했습니다.

m_nLen은 실제 데이터의 길이입니다.  연산이 끝나면, m_nLen에는 실제 데이터가 들어있는 데이터 길이만을 보관합니다.  m_nLen이 줄어든다고 해서, 재할당을 하지는 않게 하였습니다.  데이터는 m_pnData[0]의 최소비트에 LSB가 m_pnData[m_nLen-1]의 최대비트에 MSB가 저장되도록 하였습니다.

m_bNegative는 이 숫자가 음수인 경우에 true 값을 저장합니다.  정해진 비트 크기라면 2의 보수를 적용할 수 있겠지만, 여기서는 2의 보수를 적용한다는 것 자체가 무의미합니다.  그래서 m_pnData에는 항상 양수의 값만 저장을 합니다.

연산자 오버로딩과 필요한 함수들을 정의한 NxBigInt.h 헤더 파일은 다음과 같습니다.

[NxBigInt.h 소스]

#ifndef _NXBIGINT_H_
#define _NXBIGINT_H_
#include <iostream>
#include <stdint.h>

class NxBigInt;

/// @brief  Big integer class.
class NxBigInt
{
public:
    /// @brief  Constructor from C integer;
    /// @param  value                           [IN] C integer number
    NxBigInt(int value = 0);

    /// @brief  Copy constructor.
    /// @param  value                           [IN] big integer number
    NxBigInt(const NxBigInt &value);

    /// @brief  Constructor from string.
    /// @param  value                           [IN] number string
    NxBigInt(const char *value);

    /// @brief  Constructor from string.
    /// @param  pszNumberString                 [IN] number string
    NxBigInt(const wchar_t *value);

    /// @brief  Destructor.
    ~NxBigInt();

    /// @brief  Add big number and integer number.
    /// @param  value                           [IN] second parameter to add
    /// @return Return the Result of big number and integer number.
    NxBigInt operator+(int value) const;

    /// @brief  Add two big numbers.
    /// @param  value                           [IN] second parameter to add
    /// @return Return the sum of two big numbers.
    NxBigInt operator+(const NxBigInt &value) const;

    /// @brief  Add big number and integer number.
    /// @param  first                           [IN] first parameter to add
    /// @param  second                          [IN] second parameter to add
    /// @return Return the Result of big number and integer number.
    /// @note   Integer number cannot exceed unsigned short range
    friend NxBigInt operator+(int first, const NxBigInt &second);

    /// @brief  Minus sign.
    /// @return Return negative big integer.
    NxBigInt operator-() const;

    /// @brief  Subtract big number and integer number.
    /// @param  value                           [IN] second parameter to subtract
    /// @return Return the result big number.
    NxBigInt operator-(int value) const;

    /// @brief  Subtract big number from big number.
    /// @param  value                           [IN] second parameter to subtract
    /// @return Return the result big number.
    NxBigInt operator-(const NxBigInt &value) const;

    /// @brief  Subtract big number from int number.
    /// @param  first                           [IN] first parameter
    /// @param  second                          [IN] second parameter to subtract
    /// @return Return the result big number.
    friend NxBigInt operator-(int first, const NxBigInt &second);

    /// @brief  Multiply big number and integer number.
    /// @param  value                           [IN] second parameter to multiply
    /// @return Return the result of multiplying big number and integer number.
    NxBigInt operator*(int value) const;

    /// @brief  Multiply big number and integer number.
    /// @param  value                           [IN] Second parameter to multiply
    /// @return Return the result of multiplying big number and integer number.
    NxBigInt operator*(const NxBigInt &value) const;

    //  @brief  Multiply big number and integer number.
    /// @param  first                           [IN] first parameter
    /// @param  second                          [IN] second parameter
    //  @return Return the result of multiplying big number and integer number.
    friend NxBigInt operator*(int first, const NxBigInt &second);

    //  @brief  Divide big number and integer number
    //  @param  value                           [IN] second parameter to divide
    //  @return Return the Result of big number and integer number.
    NxBigInt operator/(int value) const;

    //  @brief  Divide big number and integer number
    //  @param  value                           [IN] second parameter to divide
    //  @return Return the Result of big number and integer number.
    NxBigInt operator/(const NxBigInt &value) const;

    //  @brief  Modular big number and integer number
    //  @param  value                           [IN] second parameter to divide
    //  @return Return the result of modula big number.
    NxBigInt operator%(int value) const;

    /// @brief  Shift operator.
    /// @param  value                           [IN] shift value
    /// @return Return big integer shifted by value.
    NxBigInt operator<<(int value) const;

    /// @brief  Shift operator.
    /// @param  value                           [IN] shift value
    /// @return Return big integer shifted by value.
    NxBigInt operator>>(int value) const;

    /// @brief  Assign big number with integer number
    /// @param  value                           [IN] Integer number to assign
    /// @return Return NxBigInt object.
    NxBigInt &operator=(int value);

    /// @brief  Assign big number with integer number
    /// @param  value                           [IN] Integer number to assign
    /// @return Return NxBigInt object.
    NxBigInt &operator=(int64_t value);

    /// @brief  Assign big number with string number
    /// @brief  value                           [IN] String number to assign
    /// @return Return NxBigInt object.
    NxBigInt &operator=(const char *value);

    /// @brief  Assign big number with string number
    /// @brief  value                           [IN] String number to assign
    /// @return Return NxBigInt object.
    NxBigInt &operator=(const wchar_t *value);

    /// @brief  Add big number with integer number
    /// @param  value                           [IN] value to be added
    /// @return Return added result.
    NxBigInt &operator+=(int value);

    /// @brief  Add big number with big integer.
    /// @param  value                           [IN] value to be added
    /// @return Return added result.
    NxBigInt &operator+=(const NxBigInt &value);

    /// @brief  Multiply big number with integer number.
    /// @param  value                           [IN] value to be multiplied
    /// @return Return multiplied result.
    NxBigInt &operator*=(int value);

    /// @brief  Multiply big number with big integer.
    /// @param  value                           [IN] value to be multiplied
    /// @return Return multiplied result.
    NxBigInt &operator*=(const NxBigInt &value);

    /// @brief  Divide big number with integer number.
    /// @param  value                           [IN] value to be devided
    /// @return Return devided result.
    NxBigInt &operator/=(int value);

    /// @brief  Divide big number with big integer.
    /// @param  value                           [IN] value to be devided
    /// @return Return devided result.
    NxBigInt &operator/=(const NxBigInt &value);

    /// @brief  Modula big number with big integer.
    /// @param  value                           [IN] value to be devided
    /// @return Return modula result.
    NxBigInt &operator%=(int value);

    /// @brief  Modula big number with big integer.
    /// @param  value                           [IN] value to be devided
    /// @return Return modula result.
    NxBigInt &operator%=(const NxBigInt &value);

    /// @brief  Shift big number with integer.
    /// @param  value                           [IN] value to be shifted.
    /// @return Return result big integer.
    NxBigInt &operator<<=(int value);

    /// @brief  Shift big number with integer.
    /// @param  value                           [IN] value to be shifted.
    /// @return Return result big integer.
    NxBigInt &operator>>=(int value);

    /// @brief  Type cast (bool).
    operator bool() const;

    /// @brief  Divide and store remains.
    /// @param  divisor                         [IN] divider
    /// @param  residue                         [OUT] remain number
    /// @return Return this object.
    /// @note   Big integer object will be changed after this function is called.
    NxBigInt &DivideAndStoreRemain(int divisor, int *residue);

    /// @brief  Streaming out big integer number.
    /// @param  output                          [IN] output stream
    /// @param  number                          [IN] big integer number
    /// @return Return output stream
    friend std::ostream &operator<<(std::ostream &output, const NxBigInt &number);

    /// @brief  Convert from string.
    /// @param  string                          [IN] number string
    /// @param  radix                           [IN] radix
    void ConvertFromString(const char *string, int radix = 10);

    /// @brief  Convert from string.
    /// @param  string                          [IN] number string
    /// @param  radix                           [IN] radix
    void ConvertFromString(const wchar_t *string, int radix = 10);

    /// @brief  Convert to string.
    /// @param  output                          [OUT] output buffer
    /// @param  size                            [IN] output max buffer size
    /// @param  radix                           [IN] radix
    int ConvertToString(char *output, int size, int radix = 10) const;

    /// @brief  Convert to string.
    /// @param  output                          [OUT] output buffer
    /// @param  size                            [IN] output max buffer size
    /// @param  radix                           [IN] radix
    int ConvertToString(wchar_t *output, int size, int radix = 10) const;

    /// @brief  Convert to Array.
    /// @param  output                          [OUT] output buffer
    /// @param  size                            [IN] output max buffer size
    /// @param  radix                           [IN] radix
    int ConvertToArray(uint8_t *output, int size, int radix = 10) const;

public:
    static const NxBigInt Zero;
    static const NxBigInt One;
    static const NxBigInt Undefined;

private:
    /// @brief  Get the order of value by 2.
    /// @param  value                           [IN] value
    /// @return Return the order of value by 2.
    int GetOrder2(int value);

    /// @brief  Add value.
    /// @param  value                           [IN] value
    void AddTo(int value);

    /// @brief  Add value.
    /// @param  value                           [IN] value
    void AddTo(const NxBigInt &value);

    /// @brief  Subtract value.
    /// @param  value                           [IN] value
    void SubtractTo(int value);

    /// @brief  Subtract value.
    /// @param  value                           [IN] value
    void SubtractTo(const NxBigInt &value);

    /// @brief  Multiply value.
    /// @param  value                           [IN] value
    void MultiplyTo(int value);

    /// @brief  Multiply value.
    /// @param  value                           [IN] value
    void MultiplyTo(const NxBigInt &value);

    /// @brief  Divide value.
    /// @param  value                           [IN] value
    void DivideTo(int value);

    /// @brief  Divide value.
    /// @param  value                           [IN] value
    void DivideTo(const NxBigInt &value);

    /// @brief  Modula value.
    /// @param  value                           [IN] value
    void ModulaTo(int value);

    /// @brief  Modula value.
    /// @param  value                           [IN] value
    void ModulaTo(const NxBigInt &value);

    /// @brief  Shift value.
    /// @param  value                           [IN] value
    void ShiftToLeft(int value);

    /// @brief  Shift value.
    /// @param  value                           [IN] value
    void ShiftToRight(int value);

private:
    bool m_bNegative;                           //< Negative of positive
    int m_nLen;                                 //< Length of integers' array
    int m_nSize;                                //< allocation size
    uint32_t *m_pnData;                         //< integers' array
};

#endif