How to Extract the High Part of a 64-bit Integer Multiplication in C ?

Extracting the High Part of 64-bit Integer Multiplication

In C , the multiplication of two 64-bit unsigned integers (uint64_t) results in an uint64_t that only contains the lower part of the product (i.e., (i * j) mod 2^64). If you seek to obtain the higher part of the multiplication, here are some efficient approaches:

Using 128-bit Numbers

If your compiler supports 128-bit numbers (e.g., using __uint128_t in GCC), you can perform a 128-bit multiplication and extract the upper 64 bits. This method is likely the most efficient.

Multiplication Breakdown

If your compiler does not support 128-bit numbers, you can break down each 64-bit integer into the following parts:

• a = (a_hi << 32) a_lo
• b = (b_hi << 32) b_lo

where a_hi, a_lo, b_hi, and b_lo are 32-bit unsigned integers.

Algorithm

To compute the high part of the multiplication (a_hi * b_hi), you can follow these steps:

1. Calculate the products a_hi b_hi, a_hi b_lo, b_hi a_lo, and a_lo b_lo.
2. Add the products a_hi b_hi and the upper 32 bits of the sum of a_hi b_lo and b_hi * a_lo.
3. Add the result from step 2 to the upper 32 bits of a_lo * b_lo.

注意事项

When performing these operations, you must be cautious of integer overflow. The following code illustrates how to handle overflow:

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;

uint64_t a_x_b_hi = a_hi * b_hi;
uint64_t a_x_b_mid = (a_hi * b_lo) >> 32;
uint64_t b_x_a_mid = (b_hi * a_lo) >> 32;
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 + b_x_a_mid + carry_bit;

return multhi;
Note that this code may not be perfectly accurate, but it provides a good approximation of the higher part of the multiplication.
The above is the detailed content of How to Extract the High Part of a 64-bit Integer Multiplication in C  ?. For more information, please follow other related articles on the PHP Chinese website!