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

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

C에서는 두 개의 64비트 부호 없는 정수(uint64_t)를 곱한 결과 제품의 하단 부분만 포함하는 uint64_t(예: (i * j) 모드 2^64). 곱셈의 더 높은 부분을 얻으려는 경우 다음과 같은 몇 가지 효율적인 접근 방식을 사용할 수 있습니다.

128비트 숫자 사용

컴파일러가 128비트 숫자를 지원하는 경우( 예를 들어 GCC에서 __uint128_t를 사용하면 128비트 곱셈을 수행하고 상위 64비트를 추출할 수 있습니다. 비트. 이 방법이 가장 효율적일 것입니다.

곱셈 분석

컴파일러가 128비트 숫자를 지원하지 않는 경우 각 64비트 정수를 다음과 같이 나눌 수 있습니다. 다음 부분:

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

여기서 a_hi, a_lo, b_hi 및 b_lo는 32비트 부호가 없습니다. 정수.

알고리즘

곱셈의 높은 부분(a_hi * b_hi)을 계산하려면 다음 단계를 따르세요.

1. 제품 a_hi b_hi, a_hi b_lo, b_hi a_lo 및 a_lo b_lo.
2. a_hi b_hi와 a_hi b_lo 및 b_hi * a_lo의 합의 상위 32비트를 추가합니다.
3. 2단계의 결과를 a_lo의 상위 32비트에 추가 * b_lo.

注事项

이러한 작업을 수행할 때는 정수 오버플로에 주의해야 합니다. 다음 코드는 오버플로를 처리하는 방법을 보여줍니다.

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;
이 코드는 완벽하게 정확하지는 않지만 곱셈의 더 높은 부분에 대한 좋은 근사치를 제공합니다.
위 내용은 C에서 64비트 정수 곱셈의 높은 부분을 추출하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!