C에서 64비트 정수 곱셈의 상위 부분을 추출하는 방법은 무엇입니까?

64비트 정수 곱셈의 상위 부분 추출

C에서는 두 개의 64비트 정수를 곱합니다( uint64_t ) 결과는 제품의 하위 64비트를 나타내는 값입니다. 연산은 일반적으로 낮은 비트에 원하는 나머지가 포함되는 모듈러 산술을 달성하는 데 사용됩니다. 그러나 때로는 곱셈의 높은 비트 부분도 계산해야 합니다.

최적의 솔루션

다음 시나리오를 고려하십시오.

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

128비트 숫자를 지원하는 GCC 컴파일러를 사용하는 경우 가장 효과적인 전략은 128비트 곱셈을 수행하여 상위 64비트를 추출합니다.

128비트를 지원하지 않는 대안

128비트를 지원하지 않는 경우 Yakk에서 제공하는 방법을 사용할 수 있습니다. 이 방법은 a 및 b를 각각 두 개의 32비트 숫자로 분해한 다음 64비트 곱셈을 사용하여 각각 더 작은 숫자의 곱을 계산합니다.

은 다음과 같이 분류됩니다.

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;

이제 제품은 다음과 같이 나타낼 수 있습니다.

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

그러나 64비트를 사용하여 위 수식을 계산하면 오버플로가 발생합니다. . 따라서 중간 결과에 대해 특별한 처리를 수행해야 합니다.

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

약간 수정하면 상위 부분의 추가 1에 신경 쓰지 않으면 계산을 생략할 수 있습니다. 비트를 운반하십시오.

위 내용은 C에서 64비트 정수 곱셈의 상위 부분을 추출하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!