算法-int128

严格说，int128不属于算法，但为了便于归类才标记为算法。

前言

有时候需要用到特别大的整数，比long long范围都要大，但是不想写字符串高精，怎么办？

使用int128！

使用方法

前提

使用GCC(G++)编译器时，可以使用int128类型，其它编译器的支持情况请自行尝试。

定义

int128的类型名叫做__int128，或者__int128_t（以下使用第二种表达方式）。

类似地，也存在__uint128(__uint128_t)的无符号类型。

定义时，像int变量一样定义即可。

int a = 1;
__int128_t b = 2;

注意：由于C++中数字常量最大定义为ull，所以不能直接定义一个特别大的__int128_t变量/常量。

运算

__int128_t类型的整数支持加减乘除、取模、位运算。

__int128_t a = 8;
__int128_t b = 2;
int res1 = a + b; // 10
int res2 = a - b; // 6
int res3 = a * b; // 16
int res4 = a / b; // 4
int res5 = a % b; // 0
int res6 = a ^ b; // 10

转换成字符串

C++原生的to_string函数不支持__int128_t类型，所以需要使用循环/递归。

以下是循环做法：

string to_string1(__int128_t x){
    string res = "";
    while(x > 9){
        res = to_string((int)(x % 10)) + res;
        x /= 10;
    }
    res = to_string((int)(x)) + res;
    return res;
}

以下是递归做法：

string to_string2(__int128_t x){
    if(x < 10) return to_string((int)x);
    else return to_string2(x / 10) + to_string((int)(x % 10));
}

输入/输出

对于输入，可以先输入字符串，再逐位处理。

对于输出，可以先转换成字符串再输出，也可以直接递归输出。

此处不提供代码。

范围

__int128_t的范围是：$-2^{127}\sim2^{127}-1$（$1.7 \times 10^{38}$）。

__uint128_t的范围是：$0 \sim 2^{128}$，即 $0 \sim 3.4 \times 10^{38}$。