Wie extrahiere ich den höheren Teil der 64-Bit-Ganzzahlmultiplikation in C?

Extracting the High Part of 64-bit Integer Multiplication

In C++, multiplying two 64-bit integers ( uint64_t ) results in a value representing the lower 64 bits of the product. This operation is commonly used to achieve modular arithmetic, where the lower bits contain the desired remainder. However,有时候，我们也需要计算乘法的更高位部分。

最优方案

考虑以下场景：

uint64_t i = // some value
uint64_t j = // some value
uint64_t k = mulhi(i, j); // where mulhi() returns the higher part of the 64-bit multiplication

如果使用支持 128 位数字的 GCC 编译器，最有效的策略是执行 128 位乘法并提取高 64 位。

无 128 位支持时的替代方案

如果没有 128 位支持，可以使用 Yakk 提供的方法。这个方法将 a 和 b 各分解为两个 32 位数字，然后使用 64 位乘法分别计算这些较小数字的乘积。

分解如下：

uint64_t a_lo = (uint32_t)a;
uint64_t a_hi = a >> 32;
uint64_t b_lo = (uint32_t)b;
uint64_t b_hi = b >> 32;

现在，乘积可以表示为：

a * b = ((a_hi << 32) + a_lo) * ((b_hi << 32) + b_lo)

      = ((a_hi * b_hi) << 64) +
        ((a_hi * b_lo) << 32) +
        ((b_hi * a_lo) << 32) +
          a_lo * b_lo

但是，使用 64 位对上述公式进行计算会产生溢出。因此，我们需要对中间结果进行特殊处理：

// 为防止溢出而引入的临时变量
uint64_t a_x_b_hi = a_hi * b_hi;
uint64_t a_x_b_mid = a_hi * b_lo;
uint64_t b_x_a_mid = b_hi * a_lo;
uint64_t a_x_b_lo = a_lo * b_lo;

// 计算进位位
uint64_t carry_bit = (((uint64_t)(uint32_t)a_x_b_mid +
                         (uint64_t)(uint32_t)b_x_a_mid +
                         (a_x_b_lo >> 32)) >> 32);

// 计算高位部分并返回
uint64_t multhi = a_x_b_hi +
                     (a_x_b_mid >> 32) + (b_x_a_mid >> 32) +
                     carry_bit;

return multhi;

稍做修改，如果不在意高位部分多 1，则可以省略进位位的计算。

Das obige ist der detaillierte Inhalt vonWie extrahiere ich den höheren Teil der 64-Bit-Ganzzahlmultiplikation in C?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!