How can you obtain the high part of a 64-bit integer multiplication in C ?

Obtaining the High Part of 64-Bit Integer Multiplication

In C , if i and j are 64-bit unsigned integers, i * j yields the lower 64 bits of their product, i.e., (i * j) mod 2^64. To obtain the higher part of the product, consider the following approaches:

Using 128-Bit Multiply:

If the compiler supports 128-bit integers (e.g., __uint128_t), performing a 128-bit multiply and extracting the upper 64 bits is the most efficient method.

YAK's Approach (Using 32-Bit Multiply):

This involves breaking each 64-bit integer into two 32-bit halves, multiplying them using the 64-bit multiply operation, and combining the results:

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 multhi = a_hi * b_hi + (a_hi * b_lo >> 32) + (b_hi * a_lo >> 32) + a_lo * b_lo;

Handling Overflow:

However, the above calculation performs 128-bit arithmetic, which can result in overflow. To handle this when restricted to 64-bit arithmetic, the following implementation adjusts for overflow:

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 = ((uint32_t)a_x_b_mid + (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;

Note: If an error of 1 bit in the upper 64 bits is acceptable, the calculation of the carry bit can be omitted.

The above is the detailed content of How can you obtain the high part of a 64-bit integer multiplication in C ?. For more information, please follow other related articles on the PHP Chinese website!