大貓咪的新玩具大貓咪的新玩具
文章 系列 標籤 分類 連結
大貓咪的新玩具大貓咪的新玩具

目錄

廣告 AD

目錄

比 long long int 還大的存在？探索 128 位元的整數：int128

  收錄於 C++
     約 1014 字   預計閱讀 5 分鐘    次閱讀       
比 long long int 還大的存在？探索 128 位元的整數：int128

前陣子寫程式的時候，想要減少 hash 碰撞的機率。

所以想要用比 uint64_t 更大的整數型態來計算。

但又不想用陣列存多個整數然後自己計算。

於是花了點時間研究了 __int128 和 unsigned __int128。

廣告 AD

int128 / uint128

GCC 編譯器內建支援 128 位元有符號整數 和 128 位元無符號整數。

根據查詢到的資料 1，GCC 至少從 4.1.0 版本開始就有支援，但是第一次釋出版本已經不可考了。

不同版本的名稱也不同，最一開始出來有帶 typedef 意思的 _t 結尾，在 4.1.0 版本，其名稱分別為 __int128_t 和 unsigned __int128_t，從 4.6.0 版本之後，可以使用 __int128 和 unsigned __int128 來宣告了。

雖然 4.6.0 版本之後一樣可以用帶有 _t 的來宣告，但是我在版本 12.1 版本上測試時，發現使用 unsigned __int128_t 來宣告的時候，sizeof 只有 4 bytes，使用 unsigned __int128 時一切正常，因此建議 4.6.0 版本之後都不要使用帶有 _t 的。

以下為建議的使用名稱：

GCC Version128 bits integerunsigned 128 bits integer
$<$ 4.6.0__int128_tunsigned __int128_t
$\geq$ 4.6.0__int128unsigned __int128

以下為範例：

cpp

__int128 a;
unsigned __int128 b;

如果喜歡用其他名稱的可以改為：

cpp

typedef __int128 INT128;
typedef unsigned __int128 U128;
// or
typedef __int128 int128_t;
typedef unsigned __int128 uint128_t;

如果要確認編譯器有沒有支援，可以用 macro 來測試。

cpp

#ifdef __SIZEOF_INT128__
#endif

其餘編譯器 (像是 clang) 的支援，可以參考這篇文章

由於 std::cin 和 std::cout 並不支援 128 位元的型態，因此我們需要自行撰寫輸出的函式。

輸入的方式就是直接輸入成字串，再一個 digit 一個 digit 放到 __int128，另外記得處理負號的部分。

cpp

#include <string>
#include <iostream>

using namespace std;

template<typename T>
T str2int(string str) {
    T num = 0;
    bool is_negative = (str.size() > 0 && str[0] == '-');
    for(unsigned i = (is_negative ? 1 : 0); i < str.size(); ++i) {
        num *= 10;
        num += str[i] - '0';
    }
    return (is_negative ? -num : num);
}

istream& operator>>(istream &in, __int128 &num){
    string str;
    in >> str;
    num = str2int<typeof(__int128)>(str);
    return in;
}

輸出的方式為先將數字轉成字串 (std::string)，然後再給 std::cout 輸出字串，這種方法也考慮到了正負號。

cpp

#include <ostream>
#include <string>
#include <vector>

using namespace std;

string decimal_string(__int128 num) {
    if(num == 0) return "0";
    vector<char> vec;

    bool is_negative = num < 0;
    __int128 value = is_negative ? -num : num;
    while(value != 0){
        vec.push_back((value % 10) + '0');
        value /= 10;
    }

    string str = is_negative ? "-" : "";
    return str + string(vec.rbegin(), vec.rend());
}

ostream& operator<<(ostream &out, __int128 &num){
    out << decimal_string(num);
    return out;
}

如果我們不想要每次都拿一個十進位的 digit，可以用 template 自訂成其他基數，這樣就可以一次拿出很多個十進位的 digit。

  • decimal_string 中，typename T 為被轉換的型態，這邊就是 __int128
  • T base 為拿出來的基數，但因為我們要輸出的是十進位，因此基數也要是 10 的次方數
  • typename Q 是要儲存 digit 的型態，注意型態一定要可以被 std::to_string 接受

cpp

#include <string>
#include <ostream>
#include <vector>
#include <limits>

using namespace std;

template<typename T, T base, typename Q>
string decimal_string(T num) {
    if(num == 0) return "0";

    static_assert(numeric_limits<Q>::max() >= base-1);
    static_assert(base % 10 == 0);
    vector<Q> vec;

    bool is_negative = num < 0;
    T value = is_negative ? -num : num;
    while(value != 0){
        vec.push_back(value % base);
        value /= base;
    }

    string str = is_negative ? "-" : "";
    for(int i = vec.size()-1; i >= 0; --i){
        str += to_string(vec[i]);
    }
    
    return str;
}

ostream& operator<<(ostream &out, __int128 &num){
    out << decimal_string<typeof(num), 1000000000000000ULL, uint64_t>(num);
    return out;
}

  1. Is there any way to do 128-bit shifts on gcc <4.4? ↩︎

比 long long int 還大的存在？探索 128 位元的整數：int128

PDH：使用 C++ 蒐集 Windows 上傳下載速度、CPU 使用率、硬碟讀取時間等各種效能資料

比 long long int 還大的存在？探索 128 位元的整數：int128

加速 C++ Template 編譯時間：優化編譯效率的方法

比 long long int 還大的存在？探索 128 位元的整數：int128

如何為你的 C++ 執行檔添加一個獨特的 Icon

比 long long int 還大的存在？探索 128 位元的整數：int128

C/C++ 語言：如何找最大公因數和最小公倍數

比 long long int 還大的存在？探索 128 位元的整數：int128

Uftrace：profiling 剖析程式的好工具，找出程式耗時的地方

廣告 AD
更新於 2023-06-18
閱讀原始文檔
 C++
 | 主頁