【海外記事紹介】C++で極限まで効率的な『128ビット整数』を自作する —

2月2日、Solideanが「Building Your Own Efficient uint128 in C++」と題したブログ記事を公開した。この記事では、C++において標準規格外のサイズである128ビット整数を、x64アーキテクチャの命令セットを活用して極めて効率的に自作する手法について詳しく紹介されている。

以下に、その内容を紹介する。

128ビット整数が必要とされる背景

まず、 C++の標準規格（ISO）において、128ビット整数は定義されていない* 点に注意が必要である。一般的にはコンパイラ独自の拡張（__uint128_t）や外部ライブラリが利用されるが、特定の環境（MSVCなど）への対応や、1サイクルを争うような極限の最適化が求められる現場では、自作という選択肢が浮上する。

特に、高精度な幾何計算や暗号処理といったドメインにおいては、64ビット（最大約1,800京）では不足するケースが珍しくない。かといって、メモリを動的に確保する多倍長整数ライブラリでは、計算コストの予測が困難になるという課題がある。そこで、固定幅かつハードウェアの性能を直に引き出せる「128ビット整数」が、精度の保証と速度を両立させる境界線となるのである。

基本的なデータ構造

128ビット整数を構築する最もシンプルなアイデアは、2つの64ビット整数を「下位桁（low）」と「上位桁（high）」として組み合わせることである。

#include <cstdint>
#include <immintrin.h> 

using u64 = unsigned long long;

struct u128 {
    u64 low = 0;  // 0 〜 2^64-1 までを担当
    u64 high = 0; // 2^64 以上の桁を担当
};

演算の実装：CPU命令の直接活用

この記事の核心は、加算や減算といった基本演算を、いかに「条件分岐（if文）」なしで実装するかという点にある。

加算と減算のメカニズム

筆算において、下の桁から発生する「繰り上がり（キャリー）」や「借り（ボロー）」を処理する際、通常はC++のコード上で条件判定が必要となる。しかし、x64 CPUにはこれらを管理する専用の「フラグ」が存在する。

// 加算の実装例
u128 operator+(u128 a, u128 b) {
    u128 r;
    // 下位桁を足し、発生したキャリーを c に格納する
    unsigned char c = _addcarry_u64(0, a.low, b.low, &r.low);
    // 上位桁を足す際、キャリー c も算入する
    (void)_addcarry_u64(c, a.high, b.high, &r.high);
    return r;
}

このように、イントリンシック命令（_addcarry_u64 や _subborrow_u64）を用いることで、コンパイラはCPUの adc (add with carry) や sbb (subtract with borrow) 命令を直接出力する。これにより、分岐ペナルティを回避した極めて高速な演算が可能となる。

乗算の効率化

乗算においては、128ビット×128ビットの計算を複数の64ビット乗算に分解する。BMI2命令セットの _mulx_u64 を活用し、結果が128ビットを超えて溢れる部分はあらかじめ計算対象から外すことで、最小限の命令数に抑えている。

比較演算における「ボロー」の応用

特筆すべきは、大小比較（<）の実装である。一般的な「上位桁を比較し、等しければ下位桁を比較する」という分岐アルゴリズムではなく、「実際に引き算を行ってボローが発生するかを確認する」というハードウェア寄りの手法を提案している。

bool operator<(u128 a, u128 b) {
    u64 dont_care;
    // (a - b) を行い、最終的なボローが発生すれば a < b である
    unsigned char borrow = _subborrow_u64(0, a.low, b.low, &dont_care);
    borrow = _subborrow_u64(borrow, a.high, b.high, &dont_care);
    return borrow != 0;
}

この手法により、生成されるアセンブリは cmp、sbb、setb のわずか3命令となり、ホットパス（頻繁に実行される箇所）でのパフォーマンスが劇的に向上する。

結論と展望

本記事で紹介された手法は、単に128ビット整数を作るだけでなく、ハードウェアの振る舞いを理解することで「抽象化のコスト」をゼロにするテクニックを示している。このパターンを応用すれば、192ビットや256ビットといった更なる多倍長整数への拡張も容易である。

詳細はBuilding Your Own Efficient uint128 in C++を参照していただきたい。