多倍精度整数の基礎 ( 四則演算編 )

( 次の記事 [Karatsuba乗算編](http://qiita.com/marionette-of-u/items/ec1a47e4b7701de75b63) )

## 概要
多倍精度整数は以下の式を実装する事で表現できる.

```math
\sum_{i = 0}^{n} coe_{i} \space radix^i
```

coe は次数 i ごとの任意の係数, radix は基数.
具体的には `std::vector` の template 引数に coe を指定し配列の添え字を i とする.

## 実装

### 準備
まずクラスに与えられるべき必要な template parameters を確認する.

```cpp
template<
    class UInt = std::uint16_t,
    class DoubleUInt = std::uint32_t,
    class DoubleInt = std::int32_t,
    DoubleUInt BitNum = sizeof(UInt) * CHAR_BIT
> class integer;
```

- `class UInt = std::uint16_t`
ここには coe の型を指定する. coe で表現できる最も大きな値 + 1 が radix になる.


-  `class DoubleUInt = std::uint32_t`
UInt同士の演算でキャリー等を適切に処理するために `UInt` の二倍超の値を表現できる型を指定する.


- `class DoubleInt = std::int32_t`
こちらも `class DoubleUInt = std::uint32_t` と同様の理由に拠る. ただし符号付でなければならない.

- `DoubleUInt BitNum = sizeof(UInt) * CHAR_BIT`
`UInt` の bit 数を指定する. デフォルト引数なので特に変更しなくても良いが, `int_fast8_t` 等を使用する際に手動で入力する.

### 比較
- unsigned_less, unsigned_less_eq

`unsigned_less`, `unsigned_less_eq` は `lhs` と `rhs` を符号無しの値とみなし大小を比較する.

```cpp
static bool unsigned_less(const data_type &lhs, const data_type &rhs){
    if(lhs.size() < rhs.size()){ return true; }
    if(lhs.size() > rhs.size()){ return false; }
    for(std::size_t i = lhs.size() - 1; i + 1 > 0; --i){
        if(lhs[i] < rhs[i]){ return true; }
        if(lhs[i] > rhs[i]){ return false; }
    }
    return false;
}
```

```cpp
static bool unsigned_less_eq(const data_type &lhs, const data_type &rhs){
    if(lhs.size() < rhs.size()){ return true; }
    if(lhs.size() > rhs.size()){ return false; }
    for(std::size_t i = lhs.size() - 1; i + 1 > 0; --i){
        if(lhs[i] < rhs[i]){ return true; }
        if(lhs[i] > rhs[i]){ return false; }
    }
    return true;
}
```

- operator <, operator >

`unsigned_*` とは違い, こちらは符号付の大小比較を行う.
一方が定義できればもう一方はそれを利用する事で定義できる.

```cpp
bool operator <(const integer &other) const{
    if(sign < other.sign){ return true; }
    if(sign > other.sign){ return false; }
    if(data.size() < other.data.size()){ return sign > 0; }
    if(data.size() > other.data.size()){ return sign < 0; }
    std::size_t i = data.size() - 1;
    do{
        if(data[i] < other.data[i]){ return true; }
    } while(i-- > 0);
    return false;
}
```

```cpp
bool operator >(const integer &other) const{
    return other < *this;
}
```

- operator <=, operator >=

```cpp
bool operator <=(const integer &other) const{
    if(sign < other.sign){ return true; }
    if(sign > other.sign){ return false; }
    if(data.size() < other.data.size()){ return sign > 0; }
    if(data.size() > other.data.size()){ return sign < 0; }
    std::size_t i = data.size() - 1;
    do{
        if(data[i] > other.data[i]){ return false; }
    } while(i-- > 0);
    return true;
}
```

```cpp
bool operator >=(const integer &other) const{
    return other <= *this;
}
```

- operator ==, operator !=

特に工夫する点はない.

```cpp
bool operator ==(const integer &other) const{
    return sign == other.sign && data == other.data;
}
```

```cpp
bool operator !=(const integer &other) const{
    return !(*this == other);
}
```

### 加減算
加減算は `lhs += rhs`, `lhs -= rhs` という左辺に変更を伴う処理が効率が良いため, その様に実装する.
後で融通を利かせるために符号無しのものを用意しておく.

- 加算

```cpp
void add(const integer &other){
    if(sign == other.sign){
        unsigned_add(other);
    }else{
        if(unsigned_less(data, other.data)){
            integer t(other);
            t.unsigned_sub(*this);
            data.swap(t.data);
            sign = other.sign;
        }else{ unsigned_sub(other); }
    }
}
```

- 符号無し加算

```cpp
void unsigned_add(const integer &other){
    if(data.size() < other.data.size()){
        data.resize(other.data.size());
    }

    DoubleUInt c = 0;
    std::size_t i;
    for(i = 0; i < other.data.size(); ++i){
        DoubleUInt v = static_cast<DoubleUInt>(data[i]) + static_cast<DoubleUInt>(other.data[i]) + c;
        data[i] = static_cast<UInt>(v & base_mask);
        c = v >> BitNum;
    }

    for(; c > 0; ++i){
        if(i >= data.size()){ data.resize(data.size() + 1); }
        DoubleUInt v = static_cast<DoubleUInt>(data[i]) + c;
        data[i] = static_cast<UInt>(v & base_mask);
        c = v >> BitNum;
    }
}
```

- 1word の符号無し加算. 次数付き.

```cpp
void unsigned_single_add(UInt c, std::size_t i = 0){
    if(i >= data.size()){ data.resize(i + 1); }
    for(; c > 0; ++i){
        DoubleUInt v = static_cast<DoubleUInt>(data[i]) + c;
        data[i] = static_cast<UInt>(v & base_mask);
        c = v >> BitNum;
    }
}
```

- 減算.

```cpp
void sub(const integer &other){
    if(sign != other.sign){
        unsigned_add(other);
    }else{
        if(unsigned_less(data.data, other.data)){
            integer t(other);
            t.unsigned_sub(*this);
            data.swap(t.data);
            sign = other.sign;
        }else{ unsigned_sub(other); }
    }
}
```

- 符号無し減算. 次数付き.

2の補数を使用した.

```cpp
void unsigned_sub(const integer &other, std::size_t i = 0){
    UInt c = 0;
    for(; i < other.data.size(); ++i){
        UInt t = data[i] - (other.data[i] + c);
        if(data[i] < other.data[i] + c){
            c = 1;
        }else{
            c = 0;
        }
        data[i] = t;
    }
    for(; c > 0; ++i){
        UInt t = data[i] - c;
        if(data[i] < c){
            c = 1;
        }else{
            c = 0;
        }
        data[i] = t;
    }
    normalize_data_size();
}
```

### 乗算
乗算は `result := lhs * rhs` という様に, 新たにオブジェクトを生成してそこに結果を挿入する処理が効率が良いため, その様に実装する.
こちらも符号無しがあると後々都合が良い.

- 乗算

```cpp
static integer mul(const integer &lhs, const integer &rhs){
    integer r;
    unsigned_mul(r, lhs, rhs);
    r.sign = lhs.sign * rhs.sign;
    return r;
}
```

- 符号無し乗算

```cpp
static void unsigned_mul(integer &r, const integer &lhs, const integer &rhs){
    std::size_t s = lhs.data.size() + rhs.data.size();
    r.data.resize(s + 1);
    for(std::size_t i = 0; i < lhs.data.size(); ++i){
        for(std::size_t j = 0; j < rhs.data.size(); ++j){
            DoubleUInt c = static_cast<DoubleUInt>(lhs.data[i]) * static_cast<DoubleUInt>(rhs.data[j]);
            for(std::size_t k = 0; i + j + k < s + 1; ++k){
                std::size_t u = i + j + k;
                DoubleUInt v = static_cast<DoubleUInt>(r.data[u]) + c;
                UInt a = static_cast<UInt>(v & base_mask);
                r.data[u] = a;
                c = v >> BitNum;
            }
        }
    }
    r.normalize_data_size();
}
```

- 1word の符号無し乗算

```cpp
static void unsigned_single_mul(integer &r, const integer &lhs, UInt rhs){
    std::size_t s = lhs.data.size() + 1;
    r.data.resize(s + 1);
    for(std::size_t i = 0; i < lhs.data.size(); ++i){
        DoubleUInt c = static_cast<DoubleUInt>(lhs.data[i]) * static_cast<DoubleUInt>(rhs);
        for(std::size_t k = 0; i + k < s + 1; ++k){
            std::size_t u = i + k;
            DoubleUInt v = static_cast<DoubleUInt>(r.data[u]) + c;
            UInt a = static_cast<UInt>(v & base_mask);
            r.data[u] = a;
            c = v >> BitNum;
        }
    }
    r.normalize_data_size();
}
```

### 除算
ここでは基礎的な低速な除算を扱う.

#### 準備
- 次数単位で値を左増やす = 単に先頭に n 個の 0 を追加するだけ.

```cpp
void shift_container(std::size_t n){
    data.insert(data.begin(), n, 0);
}
```

- `offset` の位置にある値を表現するのに bit 数がいくつ必要かを得る


```cpp
std::size_t bit_num(std::size_t offset) const{
    std::size_t n = 0;
    UInt x = data[offset];
    while(x > 0){
        ++n;
        x >>= 1;
    }
    return n;
}
```

- 多倍精度整数を bit 単位で left shift

処理系の定める `std::size_t` の扱える数値の大きさで制限を受ける点に注意.

```cpp
std::size_t finite_bit_shift_lsr(std::size_t n){
    std::size_t
        digit = n / static_cast<std::size_t>(BitNum),
        shift = n % static_cast<std::size_t>(BitNum),
        rev_shift = static_cast<std::size_t>(BitNum) - shift;
    UInt c = 0;
    for(std::size_t i = 0; i < data.size(); ++i){
        UInt x = data[i];
        data[i] = (x << shift) | c;
        if(rev_shift < BitNum){
            c = x >> rev_shift;
        }else{
            c = 0;
        }
    }
    if(c > 0){ data.push_back(c); }
    return digit;
}
```

- bit 単位の left shift 本体

```cpp
void bit_shift_lsr(std::size_t n){
    shift_container(finite_bit_shift_lsr(n));
}
```

- bit 単位の right shift

```cpp
void bit_shift_rsl(std::size_t n){
    std::size_t
        digit = n / static_cast<std::size_t>(BitNum),
        shift = n % static_cast<std::size_t>(BitNum),
        rev_shift = BitNum - shift,
        size = data.size();

    if(digit > 0){
        for(std::size_t i = 0, length = size - digit; i < length; ++i){
            data[i] = data[i + digit];
        }
        for(std::size_t i = 0; i < digit; ++i){
            data[size - i - 1] = 0;
        }
    }

    UInt c = 0;
    for(std::size_t i = 0; i < data.size(); ++i){
        std::size_t j = size - i - 1;
        UInt x = data[j];
        data[j] = (x >> shift) | c;
        if(rev_shift < BitNum){
            x = x << rev_shift;
        }else{
            c = 0;
        }
    }
    normalize_data_size();
}
```

- 多倍精度整数内部表現の正規化

```cpp
void normalize_data_size(){
    if(data.size() == 0 && data.front() == 0){
        data.clear();
    }else{
        std::size_t n = data.size() - 1;
        while(n > 0 && data[n] == 0){ --n; }
        data.resize(n + 1);
    }
}
```

- Quotient, Remainder を格納する構造体の定義

```cpp
struct quo_rem{
    integer quo, rem;

    quo_rem() = default;
    quo_rem(const quo_rem&) = default;
    quo_rem(quo_rem &&other) : quo(std::move(other.quo)), rem(std::move(other.rem)){}
    ~quo_rem() = default;
};
```

#### 実装
簡単にするため, bit 単位の回復型除算を実装する. まずは unsigned から.

```cpp
static quo_rem unsigned_div(const integer &lhs, const integer &rhs){
    quo_rem qr;
    qr.quo.data.reserve(lhs.data.size());
    qr.rem.data.reserve(rhs.data.size());
    qr.rem.data.push_back(0);
    for(std::size_t i = lhs.data.size() * static_cast<std::size_t>(BitNum)-1; i + 1 > 0; --i){
        qr.rem <<= 1;
        qr.rem.data[0] |= (lhs.data[i / static_cast<std::size_t>(BitNum)] >> (i % static_cast<std::size_t>(BitNum))) & 1;
        if(unsigned_less_eq(rhs.data, qr.rem.data)){
            qr.rem.unsigned_sub(rhs);
            std::size_t t = i / static_cast<std::size_t>(BitNum);
            if(qr.quo.data.size() < t + 1){ qr.quo.data.resize(t + 1); }
            qr.quo.data[t] |= 1 << (i % BitNum);
        }
    }
    return qr;
}
```

符号の処理を追記して完了.

```cpp
static quo_rem div(const integer &lhs, const integer &rhs){
    quo_rem qr = unsigned_div(lhs, rhs);
    qr.quo.sign = qr.rem.sign = lhs.sign == rhs.sign;
    return qr;
}
```

### 全体像

```cpp
#ifndef MULTI_PRECISION_INCLUDE_INTEGER_HPP
#define MULTI_PRECISION_INCLUDE_INTEGER_HPP

#include <vector>
#include <iostream>
#include <string>
#include <cstdint>
#include <climits>
#include <cmath>

namespace multi_precision{
    template<class UInt = std::uint16_t, class DoubleUInt = std::uint32_t, class DoubleInt = std::int32_t, DoubleUInt BitNum = sizeof(UInt) * CHAR_BIT>
    class integer{
    public:
        static const DoubleUInt base_mask = (static_cast<DoubleUInt>(1) << BitNum) - 1;
        static const UInt half = static_cast<UInt>(static_cast<DoubleUInt>(1) << (BitNum - 1));

        using data_type = std::vector<UInt>;
        data_type data;
        DoubleInt sign = +1;

        integer() = default;
        integer(const integer&) = default;
        integer(integer &&other) : data(std::move(other.data)), sign(other.sign){}
        integer(int x){
            if(x == 0){ return; }

            data.resize(1);
            data[0] = std::abs(x);

            sign = x >= 0 ? +1 : -1;
        }

        integer(UInt x){
            if(x == 0){ return; }

            data.resize(1);
            data[0] = x;

            sign = +1;
        }

        integer(const char *str){
            build_from_str(str);
        }

        integer(const std::string &str){
            build_from_str(str.begin());
        }

        template<class StrIter>
        void build_from_str(StrIter iter){
            if(*iter == '-'){
                sign = -1;
                ++iter;
            }

            char buff[2] = { 0 };
            while(*iter){
                buff[0] = *iter;
                int a = std::atoi(buff);
                *this *= 10;
                unsigned_single_add(a);
                ++iter;
            }
        }

        ~integer() = default;

        integer &operator =(const integer &other){
            data = other.data;
            sign = other.sign;
            return *this;
        }

        integer &operator =(integer &&other){
            data = std::move(other.data);
            sign = std::move(other.sign);
            return *this;
        }

        bool operator <(const integer &other) const{
            if(sign < other.sign){ return true; }
            if(sign > other.sign){ return false; }
            if(data.size() < other.data.size()){ return sign > 0; }
            if(data.size() > other.data.size()){ return sign < 0; }
            std::size_t i = data.size() - 1;
            do{
                if(data[i] < other.data[i]){ return true; }
            } while(i-- > 0);
            return false;
        }

        bool operator >(const integer &other) const{
            return other < *this;
        }

        bool operator <=(const integer &other) const{
            if(sign < other.sign){ return true; }
            if(sign > other.sign){ return false; }
            if(data.size() < other.data.size()){ return sign > 0; }
            if(data.size() > other.data.size()){ return sign < 0; }
            std::size_t i = data.size() - 1;
            do{
                if(data[i] > other.data[i]){ return false; }
            } while(i-- > 0);
            return true;
        }

        bool operator >=(const integer &other) const{
            return other <= *this;
        }

        bool operator ==(const integer &other) const{
            return sign == other.sign && data == other.data;
        }

        bool operator !=(const integer &other) const{
            return !(*this == other);
        }

        static bool unsigned_less(const data_type &lhs, const data_type &rhs){
            if(lhs.size() < rhs.size()){ return true; }
            if(lhs.size() > rhs.size()){ return false; }
            for(std::size_t i = lhs.size() - 1; i + 1 > 0; --i){
                if(lhs[i] < rhs[i]){ return true; }
                if(lhs[i] > rhs[i]){ return false; }
            }
            return false;
        }

        static bool unsigned_less_eq(const data_type &lhs, const data_type &rhs){
            if(lhs.size() < rhs.size()){ return true; }
            if(lhs.size() > rhs.size()){ return false; }
            for(std::size_t i = lhs.size() - 1; i + 1 > 0; --i){
                if(lhs[i] < rhs[i]){ return true; }
                if(lhs[i] > rhs[i]){ return false; }
            }
            return true;
        }

        void add(const integer &other){
            if(sign == other.sign){
                unsigned_add(other);
            }else{
                if(unsigned_less(data, other.data)){
                    integer t(other);
                    t.unsigned_sub(*this);
                    data.swap(t.data);
                    sign = other.sign;
                }else{ unsigned_sub(other); }
            }
        }

        void sub(const integer &other){
            if(sign != other.sign){
                unsigned_add(other);
            }else{
                if(unsigned_less(data.data, other.data)){
                    integer t(other);
                    t.unsigned_sub(*this);
                    data.swap(t.data);
                    sign = other.sign;
                }else{ unsigned_sub(other); }
            }
        }

        void unsigned_add(const integer &other){
            if(data.size() < other.data.size()){
                data.resize(other.data.size());
            }

            DoubleUInt c = 0;
            std::size_t i;
            for(i = 0; i < other.data.size(); ++i){
                DoubleUInt v = static_cast<DoubleUInt>(data[i]) + static_cast<DoubleUInt>(other.data[i]) + c;
                data[i] = static_cast<UInt>(v & base_mask);
                c = v >> BitNum;
            }

            for(; c > 0; ++i){
                if(i >= data.size()){ data.resize(data.size() + 1); }
                DoubleUInt v = static_cast<DoubleUInt>(data[i]) + c;
                data[i] = static_cast<UInt>(v & base_mask);
                c = v >> BitNum;
            }
        }

        void unsigned_single_add(UInt c, std::size_t i = 0){
            if(i >= data.size()){ data.resize(i + 1); }
            for(; c > 0; ++i){
                DoubleUInt v = static_cast<DoubleUInt>(data[i]) + c;
                data[i] = static_cast<UInt>(v & base_mask);
                c = v >> BitNum;
            }
        }

        void unsigned_sub(const integer &other, std::size_t i = 0){
            UInt c = 0;
            for(; i < other.data.size(); ++i){
                UInt t = data[i] - (other.data[i] + c);
                if(data[i] < other.data[i] + c){
                    c = 1;
                }else{
                    c = 0;
                }
                data[i] = t;
            }
            for(; c > 0; ++i){
                UInt t = data[i] - c;
                if(data[i] < c){
                    c = 1;
                }else{
                    c = 0;
                }
                data[i] = t;
            }
            normalize_data_size();
        }

        static void unsigned_mul(integer &r, const integer &lhs, const integer &rhs){
            std::size_t s = lhs.data.size() + rhs.data.size();
            r.data.resize(s + 1);
            for(std::size_t i = 0; i < lhs.data.size(); ++i){
                for(std::size_t j = 0; j < rhs.data.size(); ++j){
                    DoubleUInt c = static_cast<DoubleUInt>(lhs.data[i]) * static_cast<DoubleUInt>(rhs.data[j]);
                    for(std::size_t k = 0; i + j + k < s + 1; ++k){
                        std::size_t u = i + j + k;
                        DoubleUInt v = static_cast<DoubleUInt>(r.data[u]) + c;
                        UInt a = static_cast<UInt>(v & base_mask);
                        r.data[u] = a;
                        c = v >> BitNum;
                    }
                }
            }
            r.normalize_data_size();
        }

        static integer mul(const integer &lhs, const integer &rhs){
            integer r;
            unsigned_mul(r, lhs, rhs);
            r.sign = lhs.sign * rhs.sign;
            return r;
        }

        static void unsigned_single_mul(integer &r, const integer &lhs, UInt rhs){
            std::size_t s = lhs.data.size() + 1;
            r.data.resize(s + 1);
            for(std::size_t i = 0; i < lhs.data.size(); ++i){
                DoubleUInt c = static_cast<DoubleUInt>(lhs.data[i]) * static_cast<DoubleUInt>(rhs);
                for(std::size_t k = 0; i + k < s + 1; ++k){
                    std::size_t u = i + k;
                    DoubleUInt v = static_cast<DoubleUInt>(r.data[u]) + c;
                    UInt a = static_cast<UInt>(v & base_mask);
                    r.data[u] = a;
                    c = v >> BitNum;
                }
            }
            r.normalize_data_size();
        }

        struct quo_rem{
            integer quo, rem;

            quo_rem() = default;
            quo_rem(const quo_rem&) = default;
            quo_rem(quo_rem &&other) : quo(std::move(other.quo)), rem(std::move(other.rem)){}
            ~quo_rem() = default;
        };

        static quo_rem unsigned_div(const integer &lhs, const integer &rhs){
            quo_rem qr;
            qr.quo.data.reserve(lhs.data.size());
            qr.rem.data.reserve(rhs.data.size());
            qr.rem.data.push_back(0);
            for(std::size_t i = lhs.data.size() * static_cast<std::size_t>(BitNum)-1; i + 1 > 0; --i){
                qr.rem <<= 1;
                qr.rem.data[0] |= (lhs.data[i / static_cast<std::size_t>(BitNum)] >> (i % static_cast<std::size_t>(BitNum))) & 1;
                if(unsigned_less_eq(rhs.data, qr.rem.data)){
                    qr.rem.unsigned_sub(rhs);
                    std::size_t t = i / static_cast<std::size_t>(BitNum);
                    if(qr.quo.data.size() < t + 1){ qr.quo.data.resize(t + 1); }
                    qr.quo.data[t] |= 1 << (i % BitNum);
                }
            }
            return qr;
        }

        static quo_rem div(const integer &lhs, const integer &rhs){
            quo_rem qr = unsigned_div(lhs, rhs);
            qr.quo.sign = qr.rem.sign = lhs.sign == rhs.sign;
            return qr;
        }

        void shift_container(std::size_t n){
            data.insert(data.begin(), n, 0);
        }

        std::size_t bit_num(std::size_t offset = data.size() - 1) const{
            std::size_t n = 0, count = static_cast<std::size_t>(BitNum / 2);
            UInt mask = (1 << count) - 1, x = data[offset];
            while(x){
                n += x & mask > 0 ? count : 0;
                count /= 2;
                x >>= count;
                mask = (1 << count) - 1;
            }
            return n;
        }

        std::size_t finite_bit_shift_lsr(std::size_t n){
            std::size_t
                digit = n / static_cast<std::size_t>(BitNum),
                shift = n % static_cast<std::size_t>(BitNum),
                rev_shift = static_cast<std::size_t>(BitNum) - shift;
            UInt c = 0;
            for(std::size_t i = 0; i < data.size(); ++i){
                UInt x = data[i];
                data[i] = (x << shift) | c;
                if(rev_shift < BitNum){
                    c = x >> rev_shift;
                }else{
                    c = 0;
                }
            }
            if(c > 0){ data.push_back(c); }
            return digit;
        }

        void bit_shift_lsr(std::size_t n){
            shift_container(finite_bit_shift_lsr(n));
        }

        void bit_shift_rsl(std::size_t n){
            std::size_t
                digit = n / static_cast<std::size_t>(BitNum),
                shift = n % static_cast<std::size_t>(BitNum),
                rev_shift = BitNum - shift,
                size = data.size();

            if(digit > 0){
                for(std::size_t i = 0, length = size - digit; i < length; ++i){
                    data[i] = data[i + digit];
                }
                for(std::size_t i = 0; i < digit; ++i){
                    data[size - i - 1] = 0;
                }
            }

            UInt c = 0;
            for(std::size_t i = 0; i < data.size(); ++i){
                std::size_t j = size - i - 1;
                UInt x = data[j];
                data[j] = (x >> shift) | c;
                if(rev_shift < BitNum){
                    x = x << rev_shift;
                }else{
                    c = 0;
                }
            }
            normalize_data_size();
        }

        void normalize_data_size(){
            if(data.size() == 0 && data.front() == 0){
                data.clear();
            }else{
                std::size_t n = data.size() - 1;
                while(n > 0 && data[n] == 0){ --n; }
                data.resize(n + 1);
            }
        }

#define MULTI_PRECISION_ASSIGN_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(assign_op, op, type) \
    integer &operator assign_op(const type &rhs){ *this = *this op integer(rhs); return *this; }

        MULTI_PRECISION_ASSIGN_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(+= , +, int);
        MULTI_PRECISION_ASSIGN_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(-= , -, int);
        MULTI_PRECISION_ASSIGN_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(*= , *, int);
        MULTI_PRECISION_ASSIGN_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(/= , / , int);
        MULTI_PRECISION_ASSIGN_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(%= , %, int);

        MULTI_PRECISION_ASSIGN_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(+= , +, unsigned int);
        MULTI_PRECISION_ASSIGN_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(-= , -, unsigned int);
        MULTI_PRECISION_ASSIGN_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(*= , *, unsigned int);
        MULTI_PRECISION_ASSIGN_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(/= , / , unsigned int);
        MULTI_PRECISION_ASSIGN_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(%= , %, unsigned int);
    };

    template<class UInt, class DoubleUInt, class DoubleInt, DoubleUInt BitNum>
    integer<UInt, DoubleUInt, DoubleInt, BitNum> operator +(const integer<UInt, DoubleUInt, DoubleInt, BitNum> &lhs, const integer<UInt, DoubleUInt, DoubleInt, BitNum> &rhs){
        integer<UInt, DoubleUInt, DoubleInt, BitNum> t(lhs);
        t.add(rhs);
        return t;
    }

    template<class UInt, class DoubleUInt, class DoubleInt, DoubleUInt BitNum>
    integer<UInt, DoubleUInt, DoubleInt, BitNum> operator -(const integer<UInt, DoubleUInt, DoubleInt, BitNum> &lhs, const integer<UInt, DoubleUInt, DoubleInt, BitNum> &rhs){
        integer<UInt, DoubleUInt, DoubleInt, BitNum> t(lhs);
        t.sub(rhs);
        return t;
    }

    template<class UInt, class DoubleUInt, class DoubleInt, DoubleUInt BitNum>
    integer<UInt, DoubleUInt, DoubleInt, BitNum> operator *(const integer<UInt, DoubleUInt, DoubleInt, BitNum> &lhs, const integer<UInt, DoubleUInt, DoubleInt, BitNum> &rhs){
        return integer<UInt, DoubleUInt, DoubleInt, BitNum>::mul(lhs, rhs);
    }

    template<class UInt, class DoubleUInt, class DoubleInt, DoubleUInt BitNum>
    integer<UInt, DoubleUInt, DoubleInt, BitNum> operator /(const integer<UInt, DoubleUInt, DoubleInt, BitNum> &lhs, const integer<UInt, DoubleUInt, DoubleInt, BitNum> &rhs){
        return integer<UInt, DoubleUInt, DoubleInt, BitNum>::div(lhs, rhs).quo;
    }

    template<class UInt, class DoubleUInt, class DoubleInt, DoubleUInt BitNum>
    integer<UInt, DoubleUInt, DoubleInt, BitNum> operator %(const integer<UInt, DoubleUInt, DoubleInt, BitNum> &lhs, const integer<UInt, DoubleUInt, DoubleInt, BitNum> &rhs){
        return integer<UInt, DoubleUInt, DoubleInt, BitNum>::div(lhs, rhs).rem;
    }

    template<class UInt, class DoubleUInt, class DoubleInt, DoubleUInt BitNum>
    integer<UInt, DoubleUInt, DoubleInt, BitNum> operator <<(const integer<UInt, DoubleUInt, DoubleInt, BitNum> &lhs, UInt n){
        integer<UInt, DoubleUInt, DoubleInt, BitNum> x(lhs);
        x.bit_shift_lsr(n);
        return x;
    }

    template<class UInt, class DoubleUInt, class DoubleInt, DoubleUInt BitNum>
    integer<UInt, DoubleUInt, DoubleInt, BitNum> operator >>(const integer<UInt, DoubleUInt, DoubleInt, BitNum> &lhs, UInt n){
        integer<UInt, DoubleUInt, DoubleInt, BitNum> x(lhs);
        x.bit_shift_rsl(n);
        return x;
    }

    template<class UInt, class DoubleUInt, class DoubleInt, DoubleUInt BitNum>
    integer<UInt, DoubleUInt, DoubleInt, BitNum> operator +=(const integer<UInt, DoubleUInt, DoubleInt, BitNum> &lhs, const integer<UInt, DoubleUInt, DoubleInt, BitNum> &rhs){
        add(rhs);
        return *this;
    }

    template<class UInt, class DoubleUInt, class DoubleInt, DoubleUInt BitNum>
    integer<UInt, DoubleUInt, DoubleInt, BitNum> operator -=(const integer<UInt, DoubleUInt, DoubleInt, BitNum> &lhs, const integer<UInt, DoubleUInt, DoubleInt, BitNum> &rhs){
        sub(rhs);
        return *this;
    }

    template<class UInt, class DoubleUInt, class DoubleInt, DoubleUInt BitNum>
    integer<UInt, DoubleUInt, DoubleInt, BitNum> operator *=(const integer<UInt, DoubleUInt, DoubleInt, BitNum> &lhs, const integer<UInt, DoubleUInt, DoubleInt, BitNum> &rhs){
        *this = integer<UInt, DoubleUInt, DoubleInt, BitNum>::mul(lhs, rhs);
        return *this;
    }

    template<class UInt, class DoubleUInt, class DoubleInt, DoubleUInt BitNum>
    integer<UInt, DoubleUInt, DoubleInt, BitNum> &operator /=(integer<UInt, DoubleUInt, DoubleInt, BitNum> &lhs, const integer<UInt, DoubleUInt, DoubleInt, BitNum> &rhs){
        lhs = integer<UInt, DoubleUInt, DoubleInt, BitNum>::div(lhs, rhs).quo;
        return lhs;
    }

    template<class UInt, class DoubleUInt, class DoubleInt, DoubleUInt BitNum>
    integer<UInt, DoubleUInt, DoubleInt, BitNum> operator %=(integer<UInt, DoubleUInt, DoubleInt, BitNum> &lhs, const integer<UInt, DoubleUInt, DoubleInt, BitNum> &rhs){
        lhs = integer<UInt, DoubleUInt, DoubleInt, BitNum>::div(lhs, rhs).rem;
        return lhs;
    }

    template<class UInt, class DoubleUInt, class DoubleInt, DoubleUInt BitNum>
    integer<UInt, DoubleUInt, DoubleInt, BitNum> operator <<=(integer<UInt, DoubleUInt, DoubleInt, BitNum> &lhs, std::size_t n){
        integer<UInt, DoubleUInt, DoubleInt, BitNum> x(lhs);
        x.bit_shift_lsr(n);
        lhs = std::move(x);
        return lhs;
    }

    template<class UInt, class DoubleUInt, class DoubleInt, DoubleUInt BitNum>
    integer<UInt, DoubleUInt, DoubleInt, BitNum> operator >>=(integer<UInt, DoubleUInt, DoubleInt, BitNum> &lhs, std::size_t n){
        integer<UInt, DoubleUInt, DoubleInt, BitNum> x(lhs);
        x.bit_shift_rsl(n);
        lhs = std::move(x);
        return lhs;
    }

#define MULTI_PRECISION_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(op, type) \
    template<class UInt, class DoubleUInt, class DoubleInt, DoubleUInt BitNum> \
    integer<UInt, DoubleUInt, DoubleInt, BitNum> operator op(const integer<UInt, DoubleUInt, DoubleInt, BitNum> &lhs, const type &rhs){ return lhs op integer<UInt, DoubleUInt, DoubleInt, BitNum>(rhs); } \
    template<class UInt, class DoubleUInt, class DoubleInt, DoubleUInt BitNum> \
    integer<UInt, DoubleUInt, DoubleInt, BitNum> operator op(const type &lhs, const integer<UInt, DoubleUInt, DoubleInt, BitNum> &rhs){ return integer<UInt, DoubleUInt, DoubleInt, BitNum>(lhs) op rhs; }

    MULTI_PRECISION_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(+, int);
    MULTI_PRECISION_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(-, int);
    MULTI_PRECISION_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(*, int);
    MULTI_PRECISION_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(/ , int);
    MULTI_PRECISION_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(%, int);

    MULTI_PRECISION_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(+, unsigned int);
    MULTI_PRECISION_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(-, unsigned int);
    MULTI_PRECISION_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(*, unsigned int);
    MULTI_PRECISION_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(/ , unsigned int);
    MULTI_PRECISION_OPERATOR_OVERLOAD_FOR_EXPLICIT_TYPE(%, unsigned int);

    template<class UInt, class DoubleUInt, class DoubleInt, DoubleUInt BitNum>
    std::ostream &operator <<(
        std::ostream &os,
        integer<UInt, DoubleUInt, DoubleInt, BitNum> rhs
    ){
        using integer = integer<UInt, DoubleUInt, DoubleInt, BitNum>;
        std::vector<std::string> rseq;
        integer lo(10);
        for(; rhs.data.size() > 0; rhs /= lo){
            rseq.push_back(std::to_string((rhs % lo).data[0]));
        }
        os << (rhs.sign > 0 ? "" : "-");
        for(auto iter = rseq.rbegin(); iter != rseq.rend(); ++iter){
            os << *iter;
        }
        return os;
    }
}
#endif // MULTI_PRECISION_INCLUDE_INTEGER_HPP
```

### 動かしてみる
以下のコードでテストを行ってみる.

```cpp
#include <iostream>
 
int main(){
    using integer = multi_precision::integer<>;
 
    integer
        a("4967236591364265674231193736514226168778105194000932034376"),
        b("19825292459530808971875");
 
    integer t = a / b, u = a % b;
 
    std::cout << "a = " << a << std::endl;
    std::cout << "b = " << b << std::endl;
    std::cout << "t = " << t << std::endl;
    std::cout << "u = " << u << std::endl;
 
    if(a == t * b + u){
        std::cout << "success.\nYOKATTANE..." << std::endl;
    }
 
    return 0;
}
```

実行結果...

```
a = 4967236591364265674231193736514226168778105194000932034376
b = 19825292459530808971875
t = 250550482496227534224774485356120781
u = 1
success.
YOKATTANE...
```