How to Extract the High-Order Bits of a 64-Bit Integer Multiplication in C ?

Retrieving the High-Order Bits of a 64-Bit Integer Multiplication

In C , multiplying two 64-bit unsigned integers (uint64_t) results in a value that represents the low-order bits of the multiplication, effectively giving the result modulo 2^64. This raises the question of how to obtain the high-order bits, which is often necessary for certain calculations.

Implementation Approaches

1. 128-Bit Multiply:

If your compiler supports 128-bit numbers (__uint128_t), performing a 128-bit multiplication and extracting the upper 64 bits provides the most efficient way of getting the high-order bits.

2. 32-Bit Multiplication and 64-Bit Accumulation:

If 128-bit numbers are not supported, a portable and simple solution is to break down each 64-bit number into two 32-bit numbers, perform 32-bit multiplication on them, and carefully accumulate the 64-bit partial products, taking care to avoid integer overflows.

Assembly Instructions:

For some architectures like x86, there are specific assembly instructions (e.g., MULH) designed to perform such 64-bit integer multiplication. However, using these instructions in C requires knowledge of assembly programming and may not be as portable as the previously mentioned C approaches.

Example Implementation:

The following C code implements the 32-bit multiplication and 64-bit accumulation approach:

uint64_t mulhi(uint64_t a, uint64_t b) {
  uint32_t a_lo = (uint32_t)a;
  uint32_t a_hi = a >> 32;
  uint32_t b_lo = (uint32_t)b;
  uint32_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 + a_lo * b_hi; // Avoid overflow
  uint64_t b_x_a_mid = b_hi * a_lo;
  uint64_t a_x_b_lo = a_lo * b_lo;

  uint64_t multhi = a_x_b_hi +
                   (a_x_b_mid >> 32) + (b_x_a_mid >> 32) +
                   (a_x_b_lo >> 64);

  return multhi;
}

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