How to Extract the Higher Part of 64-bit Integer Multiplication 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, sometimes, we also need to calculate the higher bit part of the multiplication.

Optimal Solution

Consider the following scenario:

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

If using a GCC compiler that supports 128-bit numbers, the most effective strategy is Perform a 128-bit multiplication and extract the upper 64 bits.

Alternatives without 128-bit support

If there is no 128-bit support, you can use the method provided by Yakk. This method decomposes a and b each into two 32-bit numbers, and then uses 64-bit multiplication to calculate the product of these smaller numbers respectively.

breaks down as follows:

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;

Now, the product can be represented as:

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

However, calculating the above formula using 64 bits will produce overflow. Therefore, we need to perform special processing on the intermediate result:

// 为防止溢出而引入的临时变量
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;

With slight modification, if you don’t care about the extra 1 in the high-order part, you can omit the calculation of the carry bit.

The above is the detailed content of How to Extract the Higher Part of 64-bit Integer Multiplication in C ?. For more information, please follow other related articles on the PHP Chinese website!