> 백엔드 개발 > C++ > C에서 64비트 정수 곱셈의 높은 부분을 어떻게 얻을 수 있습니까?

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

Linda Hamilton
풀어 주다: 2024-11-12 13:09:02
원래의
804명이 탐색했습니다.

How can you obtain the high part of a 64-bit integer multiplication in C  ?

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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

원천:php.cn
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
저자별 최신 기사
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿