2つの大きな整数の乗算時にオーバーフローをキャッチして計算する

質問

私は、比較的大きな数値を乗算し、その結果を1つまたは複数の整数に格納するための効率的な（オプションとして標準的でエレガント、かつ実装が簡単な）ソリューションを探しています。

例えば、2つの64ビット整数がこのように宣言されているとします。

uint64_t a = xxx, b = yyy; 

をすると a * b を実行したとき、演算がオーバーフローしたかどうかを検出し、この場合キャリーをどこかに保存するにはどうしたらよいでしょうか？

以下のことに注意してください。 大きな数のライブラリは使いたくありません。 というのも、数字を保存する方法に制約があるからです。

どのように解決するのですか？

1. オーバーフローを検出する :

x = a * b;
if (a != 0 && x / a != b) {
    // overflow handling
}

編集: 0 (を修正しました（Markさんありがとうございます！）。

2. キャリーの計算 はかなり複雑です。1つのアプローチは、両方のオペランドをハーフワードに分割し、その後に 長い乗算 を半単語に適用することです。

uint64_t hi(uint64_t x) {
    return x >> 32;
}

uint64_t lo(uint64_t x) {
    return ((1ULL << 32) - 1) & x;
}

void multiply(uint64_t a, uint64_t b) {
    // actually uint32_t would do, but the casting is annoying
    uint64_t s0, s1, s2, s3; 
    
    uint64_t x = lo(a) * lo(b);
    s0 = lo(x);
    
    x = hi(a) * lo(b) + hi(x);
    s1 = lo(x);
    s2 = hi(x);
    
    x = s1 + lo(a) * hi(b);
    s1 = lo(x);
    
    x = s2 + hi(a) * hi(b) + hi(x);
    s2 = lo(x);
    s3 = hi(x);
    
    uint64_t result = s1 << 32 | s0;
    uint64_t carry = s3 << 32 | s2;
}

部分和自体がどれもオーバーフローしないことを確認するために、最悪のケースを考えてみます。

        x = s2 + hi(a) * hi(b) + hi(x)

を B = 1 << 32 . そして、次のようになります。

            x <= (B - 1) + (B - 1)(B - 1) + (B - 1)
              <= B*B - 1
               < B*B

少なくともSjlverのテストケースには対応しています。それ以外は未検証です (そして、もう手元に C++ コンパイラがないので、コンパイルさえできないかもしれません)。