How to Get the Upper Half of a 64-bit Integer Multiplication in C ?

Getting the Upper Half of 64-bit Integer Multiplication

In C , the multiplication of two 64-bit integers (uint64_t) results in a value that represents the lower 64 bits of the product, i.e., (i * j) mod (2^64). To obtain the upper 64 bits, various approaches can be employed.

Using 128-bit Numbers

If your compiler supports 128-bit integers (__uint128_t), the most efficient approach is to perform the multiplication using 128-bit arithmetic and extract the upper 64 bits.

Portable Approach for 64-bit Arithmetic

For compilers that do not support 128-bit numbers, a portable solution is to split each 64-bit integer into two 32-bit halves and multiply them using 64-bit multiplication. The upper halves and lower halves are then combined to calculate the full 128-bit product.

However, this calculation can result in overflows when using 64-bit arithmetic. The code below provides an implementation that handles overflows while calculating the upper 64 bits:

uint64_t mulhi(uint64_t a, uint64_t b) {
    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;
    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;
}

Note that omitting the calculation of carry_bit would result in an upper 64-bit value that may be off by 1.

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