C에서 64비트 정수 곱셈의 상위 절반을 구하는 방법은 무엇입니까?

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

C에서 두 개의 64비트 정수(uint64_t)를 곱하면 다음이 됩니다. 곱의 하위 64비트를 나타내는 값, 즉 (i * j) mod (2^64). 상위 64비트를 얻으려면 다양한 접근 방식을 사용할 수 있습니다.

128비트 숫자 사용

컴파일러가 128비트 정수(__uint128_t)를 지원하는 경우 가장 효율적인 접근 방식은 128비트 산술을 사용하여 곱셈을 수행하고 상위 64개를 추출하는 것입니다. 비트.

64비트 산술을 위한 이식 가능한 접근 방식

128비트 숫자를 지원하지 않는 컴파일러의 경우 이식 가능한 솔루션은 각 64비트 정수를 다음과 같이 분할하는 것입니다. 두 개의 32비트 반쪽을 만들고 64비트 곱셈을 사용하여 곱합니다. 그런 다음 위쪽 절반과 아래쪽 절반을 결합하여 전체 128비트 곱을 계산합니다.

그러나 이 계산은 64비트 산술을 사용할 때 오버플로가 발생할 수 있습니다. 아래 코드는 상위 64비트를 계산하는 동안 오버플로를 처리하는 구현을 제공합니다.

uint64_t mulhi(uint64_t a, uint64_t b) {
    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;
    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;
}

carry_bit 계산을 생략하면 상위 64비트 값이 1만큼 벗어날 수 있다는 점에 유의하세요.

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