Bagaimana untuk mengekstrak Bahagian Tinggi Pendaraban Integer 64-bit dalam C?

Mengekstrak Bahagian Tinggi Pendaraban Integer 64-bit

Dalam C , hasil pendaraban dua integer tidak bertanda 64-bit (uint64_t) dalam uint64_t yang hanya mengandungi bahagian bawah produk (iaitu, (i * j) mod 2^64). Jika anda ingin mendapatkan bahagian pendaraban yang lebih tinggi, berikut ialah beberapa pendekatan yang cekap:

Menggunakan Nombor 128-bit

Jika pengkompil anda menyokong nombor 128-bit ( cth., menggunakan __uint128_t dalam GCC), anda boleh melakukan pendaraban 128-bit dan mengekstrak 64 bit atas. Kaedah ini mungkin paling berkesan.

Pecahan Pendaraban

Jika pengkompil anda tidak menyokong nombor 128-bit, anda boleh memecahkan setiap integer 64-bit ke dalam bahagian berikut:

• a = (a_hi
• b = (b_hi

di mana a_hi, a_lo, b_hi dan b_lo ialah integer tidak bertanda 32-bit.

Algoritma

Untuk mengira bahagian tinggi pendaraban (a_hi * b_hi), anda boleh ikut langkah berikut:

1. Kira produk a_hi b_hi, a_hi b_lo, b_hi a_lo, dan a_lo b_lo.
2. Tambahkan produk a_hi b_hi dan 32 bit atas jumlah a_hi b_lo dan b_hi * a_lo.
3. Tambahkan hasil dari langkah 2 ke 32 bit atas a_lo * b_lo.

注意事项

Apabila melakukan operasi ini, anda mesti berhati-hati dengan limpahan integer. Kod berikut menggambarkan cara mengendalikan limpahan:

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) >> 32;
uint64_t b_x_a_mid = (b_hi * a_lo) >> 32;
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 + b_x_a_mid + carry_bit;

return multhi;

Perhatikan bahawa kod ini mungkin tidak tepat dengan sempurna, tetapi ia memberikan anggaran yang baik bagi bahagian pendaraban yang lebih tinggi.

Atas ialah kandungan terperinci Bagaimana untuk mengekstrak Bahagian Tinggi Pendaraban Integer 64-bit dalam C?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!