C에서 64비트 정수 곱셈의 고차 비트를 추출하는 방법은 무엇입니까?

64비트 정수 곱셈의 상위 비트 검색

C에서 두 개의 64비트 부호 없는 정수 곱하기(uint64_t) 결과는 곱셈의 하위 비트를 나타내는 값이 되며 결과는 효과적으로 제공됩니다. 모듈로 2^64. 이는 종종 특정 계산에 필요한 상위 비트를 얻는 방법에 대한 의문을 제기합니다.

구현 접근 방식

1. 128- 비트 곱셈:

컴파일러가 지원하는 경우 128비트 숫자(__uint128_t)는 128비트 곱셈을 수행하고 상위 64비트를 추출하는 것은 상위 비트를 얻는 가장 효율적인 방법을 제공합니다.

2. 32비트 곱셈 및 64비트 축적:

If 128비트 숫자는 지원되지 않습니다. 이식 가능하고 간단한 해결책은 각 64비트 숫자를 두 개의 32비트 숫자로 나누고, 이에 대해 32비트 곱셈을 수행하고, 주의 깊게 64비트 부분 곱을 누적하는 것입니다. 정수 오버플로를 피하세요.

조립 지침:

다음과 같은 일부 아키텍처의 경우 x86에는 이러한 64비트 정수 곱셈을 수행하도록 설계된 특정 어셈블리 명령어(예: MULH)가 있습니다. 그러나 C에서 이러한 명령어를 사용하려면 어셈블리 프로그래밍에 대한 지식이 필요하며 앞서 언급한 C 접근 방식만큼 이식성이 낮을 수 있습니다.

구현 예:

다음 C 코드 32비트 곱셈 및 64비트 누적 접근 방식을 구현합니다.

uint64_t mulhi(uint64_t a, uint64_t b) {
  uint32_t a_lo = (uint32_t)a;
  uint32_t a_hi = a >> 32;
  uint32_t b_lo = (uint32_t)b;
  uint32_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 + a_lo * b_hi; // Avoid overflow
  uint64_t b_x_a_mid = b_hi * a_lo;
  uint64_t a_x_b_lo = a_lo * b_lo;

  uint64_t multhi = a_x_b_hi +
                   (a_x_b_mid >> 32) + (b_x_a_mid >> 32) +
                   (a_x_b_lo >> 64);

  return multhi;
}

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