C에서 64비트 정수 곱셈의 높은 부분을 어떻게 얻을 수 있습니까?

64비트 정수 곱셈의 상위 부분 구하기

C에서 i와 j가 64비트 부호 없는 정수이면 i * j는 곱의 하위 64비트, 즉 (i * j) mod 2^64를 생성합니다. 제품의 더 높은 부분을 얻으려면 다음 접근 방식을 고려하십시오.

128비트 곱하기 사용:

컴파일러가 128비트 정수(예: __uint128_t)를 지원하는 경우 ), 128비트 곱셈을 수행하고 상위 64비트를 추출하는 것이 가장 효율적인 방법입니다.

YAK의 접근 방식(32비트 곱셈 사용):

여기에는 각 64비트 정수를 두 개의 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;

uint64_t multhi = a_hi * b_hi + (a_hi * b_lo >> 32) + (b_hi * a_lo >> 32) + a_lo * b_lo;

오버플로 처리:

그러나 위 계산은 128비트 연산을 수행하므로 오버플로가 발생할 수 있습니다. 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 = ((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;

참고: 상위 64비트에서 1비트의 오류가 허용되는 경우 캐리비트 계산은 생략 가능합니다.

위 내용은 C에서 64비트 정수 곱셈의 높은 부분을 어떻게 얻을 수 있습니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!