Lấy phần cao 64 bit số nguyên nhân

Question

Trong C++, nói rằng:

uint64_t i; 
uint64_t j; 

sau đó i * j sẽ mang lại một uint64_t mà đã là giá trị phần dưới của phép nhân giữa i và j, nghĩa là, (i * j) mod 2^64. Bây giờ, nếu tôi muốn phần cao hơn của phép nhân thì sao? Tôi biết rằng có tồn tại một hướng dẫn lắp ráp làm một cái gì đó như thế khi sử dụng số nguyên 32 bit, nhưng tôi không quen thuộc ở tất cả với lắp ráp, vì vậy tôi đã hy vọng giúp đỡ.

uint64_t k = mulhi(i, j); 

Answer 1

Nếu bạn đang sử dụng gcc và phiên bản bạn có hỗ trợ số 128 bit (hãy thử sử dụng __uint128_t) so với thực hiện 128 nhân và giải nén 64 bit trên có khả năng là cách hiệu quả nhất để nhận kết quả.

Nếu trình biên dịch của bạn không hỗ trợ số 128 bit, thì câu trả lời của Yakk là chính xác. Tuy nhiên, nó có thể là quá ngắn cho tiêu thụ chung. Đặc biệt, việc triển khai thực tế phải cẩn thận với việc tích luỹ 64 bit tích phân.

Giải pháp đơn giản và di động mà ông đề xuất là chia từng a và b thành 2 số 32 bit và sau đó nhân các số 32 bit đó bằng hoạt động nhân 64 bit. Nếu chúng ta viết:

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; 

sau đó rõ ràng là:

a = (a_hi << 32) + a_lo; 
b = (b_hi << 32) + b_lo; 

và:

a * b = ((a_hi << 32) + a_lo) * ((b_hi << 32) + b_lo) 
     = ((a_hi * b_hi) << 64) + 
     ((a_hi * b_lo) << 32) + 
     ((b_hi * a_lo) << 32) + 
      a_lo * b_lo 

cung cấp các tính toán được thực hiện bằng 128 bit (hoặc cao hơn) số học.

Nhưng vấn đề này yêu cầu chúng tôi thực hiện tất cả các phép tính bằng cách sử dụng số học 64 bit, vì vậy chúng tôi phải lo lắng về tình trạng tràn.

Vì a_hi, a_lo, b_hi và b_lo là tất cả các số 32 bit chưa ký, sản phẩm của chúng sẽ phù hợp với số 64 bit không dấu mà không bị tràn. Tuy nhiên, kết quả trung gian của phép tính trên sẽ không.

Đoạn mã dưới đây sẽ thực hiện mulhi (a, b) khi mathemetics phải được thực hiện theo modulo 2^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 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; 

Như Yakk chỉ ra, nếu bạn không nhớ là tắt bởi 1 trong 64 bit trên, bạn có thể bỏ qua tính toán của bit mang.

Answer 2

nhân dài nên hiệu suất ok:

cách hiệu quả nhất để làm một cái gì đó giống như là gì.

Tách a*b thành (hia+loa)*(hib+lob). Điều này cung cấp cho 4 32 bit nhân cộng với một số thay đổi. Làm chúng trong 64 bit, và làm việc mang theo cách thủ công, và bạn sẽ nhận được phần cao.

Lưu ý rằng gần đúng phần cao có thể được thực hiện với số nhân ít hơn - chính xác trong vòng 2^33 hoặc hơn với 1 nhân, và trong 1 với 3 nhân.

Tôi không nghĩ rằng có một giải pháp thay thế di động.